Yogurt factory

Interview

Time limit1sMemory limit1024 MB

Summary

Given weekly production costs, delivery quantities, and a per-week storage fee, find the minimum total cost to meet every week's delivery.

Level: Medium5 of 10
Topics: Greedy, Dynamic programming
Solved: No attempts yet

Problem

The cows have purchased a yogurt factory that makes world-famous Yucky Yogurt. Over the next $N$ ( $1 \le N \le 10,000$ ) weeks, the price of milk and labor fluctuates weekly, so producing one unit of yogurt in week $i$ costs the company $C_i$ cents ( $1 \le C_i \le 5,000$ ). The factory is well designed and can produce arbitrarily many units of yogurt each week.

Yucky Yogurt owns a warehouse that stores unused yogurt at a constant fee of $S$ ( $1 \le S \le 100$ ) cents per unit per week. Yogurt does not spoil. The warehouse is enormous and can hold arbitrarily many units.

Yucky wants to make weekly deliveries of $Y_i$ ( $0 \le Y_i \le 10,000$ ) units of yogurt to its clients, where $Y_i$ is the delivery quantity in week $i$ . Find a schedule that minimizes the total cost over the $N$ weeks. Yogurt produced in week $i$ , as well as yogurt already in storage, can be used to meet the demand for that week.

Input

The first line contains two space-separated integers $N$ and $S$ .

Line $i+1$ (for $1 \le i \le N$ ) contains two space-separated integers $C_i$ and $Y_i$ .

Output

The first line contains a single integer, the minimum total cost to satisfy the yogurt schedule. The total may not fit in a 32-bit integer.

Hint

In week 1, produce 200 units of yogurt and deliver all of it. In week 2, produce 700 units: deliver 400 units while storing 300 units. In week 3, deliver the 300 units that were stored. In week 4, produce and deliver 500 units.

Examples1

Example 1
Input
```
4 5
88 200
89 400
97 300
91 500
```
Expected output
```
126900
```