P5095 [USACO12OPEN] Bookshelf S

Farmer John likes to sit down and read when he has nothing to do. Over the years, he has collected a total of $N$ books ($1 \leq N \leq 2000$), and he plans to build a new bookshelf to hold these books. Each book has a width $w_i$ and a height $h_i$. The books must be placed in order (that is, the books placed on the same shelf layer must form a consecutive interval). The total width of each shelf layer cannot exceed $L$ ($1 \leq L \leq 10^9$). The height of a shelf layer equals the height of the tallest book on that layer, and the total height of the bookshelf equals the sum of the heights of all layers. Now please help FJ find the minimum possible total height of the bookshelf.

The first line contains two integers $N, L$. The next $N$ lines each contain two integers $h_i, w_i$ ($1 \leq h_i \leq 10^6$, $1 \leq w_i \leq L$).

Output one integer, the minimum possible height of the bookshelf.

Put the first book on the first layer, the second, third, and fourth books on the second layer, and the fifth book on the third layer. The total height is $5+13+3=21$. It can be proven that there is no better arrangement. Translated by ChatGPT 5