← 返回题目列表

AtCoder · jag2017summer_day3_i

I. 图书馆员的工作

中文机器翻译题面 查看原题

问题陈述

日本动物女孩图书馆(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