사서의 업무

Japanese Animal Girl Library(JAG Library)는 긴 책장으로 유명하다. 책장에는 책 $N$권이 왼쪽에서 오른쪽으로 $1$번부터 $N$번까지 번호가 붙어 있다. $i$번째 책의 무게는 $w_i$이다.

어느 날, 장난꾸러기 여우 Jiro가 책장에 있는 책의 순서를 뒤섞었다! 순서는 왼쪽에서 오른쪽으로 순열 $b_1, \ldots, b_N$이 되었다. JAG Library의 사서인 여우 Hanako는 원래 순서를 되돌려야 한다. 그녀는 책의 순열 $p_1, \cdots, p_N$에 대해 아래에 설명한 작업 A 또는 작업 B 중 하나를, $1 \le l < r \le N$인 임의의 두 정수 $l$과 $r$로 수행해서 책의 순서를 바꿀 수 있다.

작업 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}$ 사이의 책을 오른쪽으로 옮긴다.
• 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)$의 순열이다.

노동력 합의 최솟값을 한 줄에 출력한다.