Bookshelf

Interview

Time limit1sMemory limit128 MB

Summary

Partition the books, in order, into shelves of total width at most L to minimize the sum of each shelf's max height.

Level: Medium7 of 10
Topics: Dynamic programming, Segment tree, Stack
Solved: No attempts yet

Problem

Farmer John has collected $N$ books ( $1 \le N \le 100000$ ) and wants to build a set of bookshelves to hold them all.

Each book $i$ has a width $W(i)$ and a height $H(i)$ . The books must be placed on the shelves in order: the first shelf holds books $1 \dots k$ for some $k$ , the second shelf starts with book $k+1$ , and so on. Each shelf can hold a total width of at most $L$ ( $1 \le L \le 10^9$ ).

The height of a shelf equals the height of the tallest book on it, and the total height of the bookshelf set is the sum of the heights of all shelves (they are stacked vertically).

Compute the minimum possible total height of the bookshelf set.

Input

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

Each of the next $N$ lines contains two space-separated integers $H(i)$ and $W(i)$ , the height and width of book $i$ ( $1 \le H(i) \le 10^6$ , $1 \le W(i) \le L$ ).

Output

Print a single integer: the minimum possible total height of the bookshelf set.

Explanation

In the first example there are $5$ books and each shelf may hold a total width of at most $10$ . One optimal arrangement uses $3$ shelves: the first holds only book $1$ (height $5$ , width $7$ ), the second holds books $2 \dots 4$ (heights $9, 8, 13$ , so the shelf height is $13$ and the total width is $9$ ), and the third holds book $5$ (height $3$ , width $8$ ). The total height is $5 + 13 + 3 = 21$ .

Examples3

Example 1
Input
```
5 10
5 7
9 2
8 5
13 2
3 8
```
Expected output
```
21
```
Example 2
Input
```
1 5
1000000 3
```
Expected output
```
1000000
```
Example 3
Input
```
6 6
4 3
1 3
6 2
2 4
5 1
3 5
```
Expected output
```
15
```