Bookshelf

When Farmer John isn't milking cows, stacking haybales, lining up his cows, or building fences, he enjoys sitting down with a good book. Over the years he has collected $N$ books ($1 \le N \le 2\,000$), and he wants to build a new 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 onto the shelves in the given order: the first shelf holds books $1 \dots k$ for some $k$, the second shelf starts with book $k+1$, and so on. The total width of the books on any single shelf may be at most $L$ ($1 \le L \le 10^9$). The height of a shelf equals the height of the tallest book on it, and because the shelves are stacked vertically, the height of the whole bookcase is the sum of the heights of all the shelves.

Compute the minimum possible height of the entire bookcase.

• Line 1: two space-separated integers $N$ and $L$.
• Lines 2 to $N+1$: line $i+1$ contains two space-separated integers, the height $H_i$ and the width $W_i$ of book $i$ ($1 \le H_i \le 10^6$, $1 \le W_i \le L$).

• Print the minimum possible total height of the bookcase on a single line.

Input Details

There are 5 books, and each shelf may hold books whose total width is at most $10$.

Output Details

The books are placed on 3 shelves: the first holds only book 1 (height 5, width 7), the second holds books $2 \dots 4$ (height 13, total width 9), and the third holds book 5 (height 3, width 8).