Minimum Shelf Height

You are given a sequence of books where each book is represented by two integers: its thickness and its height. The books must be placed on a shelf in the given order. Books are arranged from left to right in a row, and if adding a book would cause the total thickness to exceed the shelf's width, you must start a new row.

The height of each row is determined by the maximum height of the books in that row, and the total shelf height is the sum of the heights of all rows. Formally, if a row contains books with heights \(h_1, h_2, \dots, h_k\), its height is \(\max\{h_1, h_2, \dots, h_k\}\), and the objective is to minimize the total height:

\(\min \sum_{\text{rows}} \max\{\text{height of books in the row}\}\), subject to \(\sum_{\text{books in row}} \text{thickness} \leq \text{shelf\_width}\).

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers: n (the number of books) and shelf_width (the maximum allowed total thickness per row).
• Then follow n lines, each containing two integers. The first integer is the thickness and the second is the height of the book.

outputFormat

Output the minimum total shelf height needed to accommodate all the books while respecting the shelf width, formatted to exactly two decimal places. The output should be written to standard output (stdout).

4 6
1 3
2 4
3 5
4 6

11.00