MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 16px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

Japanese Animal Girl Library (JAG Library) is famous for a long bookshelf. It contains $N$ books numbered from $1$ to $N$ from left to right. The weight of the $i$-th book is $w\_i$.

One day, naughty Fox Jiro shuffled the order of the books on the shelf! The order has become a permutation $b\_1, \\ldots, b\_N$ from left to right. Fox Hanako, a librarian of JAG Library, must restore the original order. She can rearrange a permutation of books $p\_1, \\cdots, p\_N$ by performing either operation A or operation B described below, with arbitrary two integers $l$ and $r$ such that $1 \\le l < r \\le N$ holds.

Operation A:

• A-1. Remove $p\_l$ from the shelf.
• A-2. Shift books between $p\_{l+1}$ and $p\_r$ to left.
• A-3. Insert $p\_l$ into the right of $p\_r$.

Operation B:

• B-1. Remove $p\_r$ from the shelf.
• B-2. Shift books between $p\_l$ and $p\_{r-1}$ to right.
• B-3. Insert $p\_r$ into the left of $p\_l$.

This picture illustrates the orders of the books before and after applying operation A and B for $p=(3,1,4,5,2,6)$, $l=2$, $r=5$.

Since the books are heavy, operation A needs $\\sum\_{i=l+1}^{r} w\_{p\_i} + C \\times (r-l) \\times w\_{p\_l}$ units of labor and operation B needs $\\sum\_{i=l}^{r-1} w\_{p\_i} + C \\times (r-l) \\times w\_{p\_r}$ units of labor, where $C$ is a given constant positive integer.

Hanako must restore the initial order from $b\_1, \\cdots, b\_N$ by performing these operations repeatedly. Find the minimum sum of labor to achieve it.

Input

The input consists of a single test case formatted as follows.

$N \\ C$ $b\_1 \\ w\_{b\_1}$ $\\vdots$ $b\_N \\ w\_{b\_N}$

The first line conists of two integers $N$ and $C \\ (1 \\le N \\le 10^5, 1 \\le C \\le 100)$. The $(i+1)$-th line consists of two integers $b\_i$ and $w\_{b\_i} \\ (1 \\le b\_i \\le N, 1 \\le w\_{b\_i} \\le 10^5)$. The sequence $(b\_1, \\ldots, b\_N)$ is a permutation of $(1, \\ldots, N)$.

Output

Print the minimum sum of labor in one line.

Sample Input 1

3 2
2 3
3 4
1 2

Output for Sample Input 1

15

Performing operation B with $l=1, r=3$, i.e. removing book 1 then inserting it into the left of book 2 is an optimal solution. It costs $(3 + 4) + 2 \\times 2 \\times 2 = 15$ units of labor.

Sample Input 2

3 2
1 2
2 3
3 3

Output for Sample Input 2

0

Sample Input 3

10 5
8 3
10 6
5 8
2 7
7 6
1 9
9 3
6 2
4 5
3 5

Output for Sample Input 3

824