### 问题描述 在一个新兴的科技园区，有 $n$ 个技术公司正在筹建办公室，这些办公室排成一行，总共有 $m$ 个位置，编号从 $1$ 到 $m$（包括两端的位置）。位置 $u$ 和 $v$ 被认为是相邻的，当且仅当它们的编号之差的绝对值为 $1$。每个公司需要分配一个办公室，且要求每个办公室只能容纳一个公司。如果两个公司办公室相邻，它们将成为邻居。 不同的公司有不同的偏好，有的公司喜欢与邻居共享资源，而有的公司更倾向于独自工作。对于第 $i$ 个公司，如果他至少有一个邻居公司，则他的不满意度为 $a_i$；如果他没有邻居公司，则他的不满意度为 $b_i$。 作为科技园区的规划者，您的目标是通过合理的办公室分配方案，最小化所有公司的不满意度之和。 ### 输入格式 第一行输入两个正整数 $n$、$m$，表示公司的数量和办公室的数量。 接下来 $n$ 行，第 $i+1$ 行输入两个空格隔开的整数 $a_i$、$b_i$，表示第 $i$ 家公司至少有一个邻居公司的不满意度和没邻居公司的不满意度。 ### 输出格式 输出 $1$ 个整数，表示所有公司的不满意度之和的最小值。 ### 样例输入 ```text 2 3 1 10 2 2 ``` ### 样例输出 ```text 3 ``` ### 说明 样例中，第 $1$ 家公司在第一个位置，第 $2$ 家公司在第二个位置，不满意度为 $1+2=3$。 ### 评测数据规模 对于所有评测数据，$1\leq n \leq 10^5$，$n \leq m \leq 10^6$，$1\leq a_i,b_i \leq 10^6$。