There are $n$ jobs, numbered $1, 2, \dots, n$, waiting to be processed in batches on a supercomputer. The task is to divide these $n$ jobs into several batches, where each batch consists of a sequence of contiguous jobs. Processing starts at time $0$. Before each batch begins, there is a setup time $S$, and the time required to process a batch is the sum of the individual processing times of the jobs in that batch. The time required to process job $i$ individually is $t_i$, and the resource cost is its completion time multiplied by a cost coefficient $f_i$. All jobs in the same batch are completed at the same time. For example, if a batch of jobs $x, x+1, \dots, x+k$ starts at time $T$, the completion time for all jobs in this batch is $T + S + (t_x + t_{x+1} + \dots + t_{x+k})$. The optimal batch processing problem is to determine a batching scheme that minimizes the total cost. For example, suppose there are 5 jobs waiting to be processed, with $S=1$, $(t_1, t_2, t_3, t_4, t_5) = (1, 3, 4, 2, 1)$, and $(f_1, f_2, f_3, f_4, f_5) = (3, 2, 3, 3, 4)$. If the batching scheme $\{1, 2\}, \{3\}, \{4, 5\}$ is used, the completion times for the jobs are $(5, 5, 10, 14, 14)$, and the resource costs for the jobs are $(15, 10, 30, 42, 56)$, resulting in a total cost of $153$.

Input

The first line contains the number of jobs $n$. The second line contains the setup time $S$. Each of the following $n$ lines contains two integers: the time $t_i$ required to process job $i$ individually and its cost coefficient $f_i$.

$n, S, t_i, f_i$ are all positive integers, $S \le 50$, and $t_i, f_i \le 100$.

• For 30% of the test data, $n \le 50$.
• For 50% of the test data, $n \le 500$.
• For 70% of the test data, $n \le 2000$.
• For 100% of the test data, $n \le 10000$.

Output

Output the minimum total cost.

Examples

Input 1

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

Output 1

153