Book Shelf Optimization

Farmer John has collected N books and intends to build a new bookshelf to house them. Each book has a width \(w_i\) and a height \(h_i\). The books must be placed in order, meaning that books on the same shelf must form a contiguous segment. Each shelf can hold books whose total width does not exceed \(L\). The height of a shelf is determined by the maximum height of the books in that shelf, and the total height of the bookshelf is the sum of the heights of all shelves.

Your task is to minimize the total height of the bookshelf given the books' dimensions. Formally, let the books be numbered from 1 to \(N\). For any segment of books from \(j\) to \(i\) that you place on a shelf, the following must hold:

• \(\sum_{k=j}^i w_k \leq L\)
• The shelf height is \(\max_{k=j}^i h_k\).

You need to partition the books into consecutive segments such that the sum of the shelf heights is minimized.

inputFormat

The first line contains two integers \(N\) and \(L\) (\(1 \leq N \leq 2000\), \(1 \leq L \leq 10^9\)). Each of the following \(N\) lines contains two integers \(w_i\) and \(h_i\), representing the width and height of the \(i\)-th book.

outputFormat

Output a single integer: the minimum total height of the bookshelf.

sample

3 10
1 1
2 3
3 2

3