You have $n$ cubic blocks, numbered from 1 to $n$. Block number $i$ has dimensions $a_i \times a_i \times a_i$ and is painted with pattern $w_i$ (patterns are identified by integers).

Your goal is to build a tower with the highest possible score using a selection of blocks. The tower should consist of a certain number of blocks, placed flat, one on top of another. Let $j_1, \dots, j_m$ denote the numbers of the blocks chosen to build the tower (where $m$ is the number of chosen blocks), in order from the base to the top. The tower is evaluated according to the following criteria:

• Stability. The tower is stable if each subsequent block is strictly smaller, i.e., $a_{j_x} > a_{j_{x+1}}$. Unstable towers receive a score of 0, regardless of the other criteria.
• Height. If the tower has height $h = a_{j_1} + \dots + a_{j_m}$, the score is increased by the value $h$.
• Style points. Adjacent blocks with different patterns (i.e., $w_{j_x} \neq w_{j_{x+1}}$) spoil the aesthetics, so for each such pair of adjacent blocks, the score is reduced by a penalty $c$.

Input

The first line of input contains two integers $n$ and $c$ ($1 \le n, c \le 500\,000$), representing the number of available blocks and the penalty for adjacent blocks with different patterns, respectively.

The next $n$ lines contain descriptions of the individual blocks. The description of block number $i$ is in the $i$-th line and consists of two integers $a_i$ and $w_i$ ($1 \le a_i, w_i \le 500\,000$), representing the side length of the cubic block and the pattern number. The blocks are given in order of non-decreasing size, i.e., $a_i \le a_{i+1}$.

In tests worth 5 points, the following additional condition holds: $a_i < a_{i+1}$.

Output

The output should contain a single integer — the score of the best tower that can be built from the blocks provided in the input.

Examples

Input 1

4 1
1 1
3 2
4 3
4 1

Output 1

6

Input 2

4 5
1 1
3 2
4 3
4 1

Output 2

5

Note

Figure 1: The set of four blocks is the same in both tests. The tests differ only by the penalty c. In the first test c = 1, and in the second c = 5.

Figure 2: The best towers for the first test. Height 8 and double penalty. The score is 8 - 2 * 1 = 6. For penalty c = 5, these towers have a low score of 8 - 2 * 5 = -2.

Figure 3: The best tower for the second test. Height 5 and no penalty, because the blocks have the same pattern. The score is 5 - 0 * c = 5.