P1376 [USACO05MAR] Yogurt factory Machine Factory

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.

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

Output a single integer, the minimum cost.

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