Problem Description

All residents of Lanqiao Village live along a road of length $L$. The position of each household is measured by its distance from the start of the road. The distance of household $i$ from the start is $d_i$.

Every year, Lanqiao Village holds a gathering. This year, because the population is too large, the village committee decides to hold gatherings at $4$ locations: $3$ of them are in the middle of the road, and $1$ is at the end of the road.

It is known that each household will attend a gathering in the direction away from the start of the road (i.e., towards increasing distance). The travel cost for a household is the product of the number of people in the household $t_i$ and the travel distance.

Given each household's position $d_i$ and population $t_i$, find the best gathering locations $p_1,p_2,p_3,p_4\ (p_1 \le p_2 \le p_3 \le p_4 = L)$ such that the total travel cost of all people in the village is minimized.

Input Format

The first line contains two integers $n, L$, representing the number of households in Lanqiao Village and the length of the road.

The next $n$ lines each contain two integers $d_i, t_i$, representing the distance of household $i$ from the start of the road and the number of people in the household.

Output Format

Output one line containing one integer, representing the total travel cost of all people in the village.

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

18

Hint

[Sample Explanation]

If gatherings are held at distances $2, 5, 8, 10$ from the start, the distances that the $6$ households need to walk are $1, 0, 1, 0, 2, 0$, respectively. The total travel cost is $1 \times 3 + 0 \times 2 + 1 \times 5 + 0 \times 20 + 2 \times 5 + 0 \times 7 = 18$.

[Constraints]

For $10\%$ of the testdata, $1 \le n \le 300$.

For $30\%$ of the testdata, $1 \le n \le 2000$, $1 \le L \le 10000$, $0 \le d_i \le L$, $d_i \le d_{i+1}$, $0 \le t_i \le 20$.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le L \le 10^6$, $0 \le d_i \le L$, $d_i \le d_{i+1}$, $0 \le t_i \le 10^6$.

Translated by ChatGPT 5