Word Clouds Revisited

Tagg Johnson writes software that draws word clouds. A word cloud is a picture of textual data in which the size of the bounding box of each word depends on how often that word appears in the source text.

Tagg ran into an oddity in the algorithm he uses to lay entries out in rows. A cloud has a fixed maximum width, and Tagg wants the total height to be as small as possible. The entries must be placed in a given order. Each entry goes either immediately to the right of the previous entry in the same row, or at the far left of a new row. The height of a row is the largest height among the entries placed in that row, and the height of the cloud is the sum of the row heights.

Tagg's original algorithm keeps each entry in the row of the previous entry unless it no longer fits within the width limit. Figure 1 shows what that algorithm produces for one cloud with a maximum width of 260 units.

Figure 1: the placement Tagg's original algorithm produces

The first three entries go in the first row, for a total width of 238. The fourth and fifth entries share the second row, for a total width of 193. The sixth entry sits alone on the last row. The three rows have heights 48, 43 and 23, so the cloud is $48 + 43 + 23 = 114$ units tall.

Tagg later noticed that the same data allows a better cloud, shown in Figure 2. Putting the first and second entries in one row, the third and fourth in the next row, and the fifth and sixth in a third row gives a total height of only $23 + 48 + 28 = 99$ units, still within the width limit of 260.

Figure 2: an optimal placement of the entries from Figure 1

Given the list of entries and the maximum width, build the word cloud of minimum height.

The first line contains two integers $N$ and $C$, where $N$ ($2 \le N \le 5000$) is the number of entries to place and $C$ ($150 \le C \le 1000$) is the maximum width of the cloud.

Each of the next $N$ lines contains two integers $w$ and $h$ ($10 \le w \le 150$, $10 \le h \le 150$), the width and the height of one entry. The entries are given in the order in which they must be laid out.

Print the minimum height the word cloud needs under the rules above.