Description

Xiao T opened a machine factory. Over $N$ weeks, raw material costs and labor prices fluctuate; in week $i$, producing one machine costs $C_i$ yuan. If a machine is not sold, maintaining each machine costs $S$ yuan per week; this fee is constant.

The factory has received orders: in week $i$, it must deliver $Y_i$ machines to the client. Machines produced in week $i$, as well as inventory from previous weeks, can be used to fulfill the order.

Please compute the minimum total cost to complete all orders over these $N$ weeks.

Input Format

The first line contains two integers $N$ and $S$. The next $N$ lines each contain two integers $C_i$ and $Y_i$.

Output Format

Output a single integer, the minimum cost.

4 5
88 200
89 400
97 300
91 500

126900

Hint

For $100\%$ of the testdata, $1 \le N \le 10^4$, $1 \le C_i \le 5000$, $1 \le S \le 100$, $0 \le Y_i \le 10^4$.

Translated by ChatGPT 5