There are $n$ tasks to be processed on a machine, forming a sequence. These tasks are labeled $1$ to $n$, so the sequence is $1, 2, 3, \dots, n$. The $n$ tasks are divided into several batches, where each batch consists of a contiguous sequence of tasks. Starting from time $0$, these tasks are processed in batches. The time required to complete the $i$-th task individually is $T_i$. Before each batch of tasks begins, the machine requires a setup time $s$, and the time required to complete a batch is the sum of the times required for each task in that batch.

Note that all tasks in the same batch are completed at the same time. The cost for each task is its completion time multiplied by a cost coefficient $C_i$.

Please determine a grouping scheme that minimizes the total cost.

Input

The first line contains an integer $n$.

The second line contains an integer $s$.

The next $n$ lines each contain a pair of integers, $T_i$ and $C_i$, representing the time required to complete the $i$-th task individually and its cost coefficient $C_i$, respectively.

Output

A single integer representing the minimum total cost.

Examples

Input 1

5
1
1 3
3 2
4 3
2 3
1 4

Output 1

153

Subtasks

For $100\%$ of the data, $1 \le n \le 3 \times 10^5$, $1 \le s \le 2^8$, $\left| T_i \right| \le 2^8$, $0 \le C_i \le 2^8$.