Bookshelf Optimization

Farmer John has collected N books, and he wishes to arrange them on bookshelves. Book i has width \(W(i)\) and height \(H(i)\). The books must be placed in order: the first shelf contains books 1 through k, the second shelf starts with book \(k+1\), and so on.

Each shelf has a maximum total width of \(L\). The height of a shelf is equal to the height of the tallest book on that shelf. The total height of the bookshelf arrangement is the sum of the individual shelf heights. The goal is to determine the minimum possible total height for the entire set of bookshelves.

A formal recurrence for the dynamic programming solution is given by:

\[ \text{dp}[i] = \min_{j \le i \text{ and } \sum_{k=j}^{i} W(k) \le L} \Bigl\{\text{dp}[j-1] + \max_{k=j}^{i} H(k)\Bigr\} \]

with \(\text{dp}[0] = 0\).

inputFormat

The first line contains two integers \(N\) and \(L\): the number of books and the maximum allowed width per shelf.

Each of the next \(N\) lines contains two integers \(W(i)\) and \(H(i)\), representing the width and height of the \(i^{th}\) book.

\(1 \le N \le 100{,}000\), \(1 \le L \le 10^9\).

outputFormat

Output a single integer representing the minimum total height of the arranged bookshelves.

sample

3 10
1 1
2 3
3 2

3