问题陈述
日本动物女孩图书馆(JAG Library)以长书架而闻名。它包含 $N$ 本书,从左到右编号为 $1$ 到 $N$。第 $i$ 本书的重量为 $w_i$。
有一天,调皮的狐狸二郎打乱了书架上的书的顺序!顺序变成了从左到右的排列 $b_1, \ldots, b_N$。 JAG 图书馆的图书管理员 Fox Hanako 必须恢复原来的秩序。她可以通过执行下面描述的操作 A 或操作 B 来重新排列书籍 $p_1, \cdots, p_N$ 的排列,其中任意两个整数 $l$ 和 $r$ 使得 $1 \le l < r \le N$ 成立。
操作A:
- A-1。从架子上删除 $p_l$。
- A-2。将书籍在 $p_{l+1}$ 和 $p_r$ 之间移动到 左.
- A-3。将 $p_l$ 插入 对 $p_r$ 的 。
操作B:
- B-1。从架子上删除 $p_r$。
- B-2。将书籍在 $p_l$ 和 $p_{r-1}$ 之间移动到 对 $p_r$ 的.
- B-3。将 $p_r$ 插入 $p_l$ 的 左 。
这张图展示了对 $p=(3,1,4,5,2,6)$、$l=2$、$r=5$ 应用操作 A 和 B 之前和之后的书籍顺序。

由于书本较重,操作 A 需要 $\sum_{i=l+1}^{r} w_{p_i} + C \times (r-l) \times w_{p_l}$ 单位劳动力,操作 B 需要 $\sum_{i=l}^{r-1} w_{p_i} + C \times (r-l) \times w_{p_r}$ 单位劳动力,其中 $C$ 是给定的常量正整数。
Hanako 必须通过重复执行这些操作来恢复 $b_1, \cdots, b_N$ 的初始顺序。求出实现这一目标所需的最少劳动量。
输入
输入由单个测试用例组成,格式如下。
$N\C$ $b_1 \ w_{b_1}$ $\vdots$ $b_N \ w_{b_N}$
第一行由两个整数 $N$ 和 $C \ (1 \le N \le 10^5, 1 \le C \le 100)$ 组成。 第 $(i+1)$ 行由两个整数 $b_i$ 和 $w_{b_i} \ (1 \le b_i \le N, 1 \le w_{b_i} \le 10^5)$ 组成。 序列 $(b_1, \ldots, b_N)$ 是 $(1, \ldots, N)$ 的排列。
输出
在一行中打印最少的劳动力总和。
示例输入 1
3 2 2 3 3 4 1 2
样本输入 1 的输出
15
在 $l=1, r=3$ 的情况下执行操作 B,即移除书本 1,然后将其插入到书本 2 的左侧,这是最佳解决方案。其成本为 $(3 + 4) + 2 \times 2 \times 2 = 15$ 单位劳动力。
示例输入 2
3 2 1 2 2 3 3 3
样本输入 2 的输出
0
示例输入 3
10 5 8 3 10 6 5 8 2 7 7 6 1 9 9 3 6 2 4 5 3 5
样本输入 3 的输出
824