Bookcase

Assignment

Sally and Mark plan to get a new bookcase for their books. They are debating about its design. The bookcase will consist of several shelves of the same length. Mark thinks it is a good idea to set heights between shelves variably so that the placed books just fit in. If the books are put onto shelves by their heights, this might result in a bookcase of smaller height. However, Sally does not agree. She wants to keep the books alphabetically ordered by the author and title. Mark is not happy with this requirement, but he must accept it. After some thinking he believes he can find an optimal solution even for the alphabetical ordering. He realizes that some books arrangements that do not necessary fill each of the shelves to the end might give better results. Sally is not thrilled even by this proposal. She worries there might be large, ugly looking gaps at the shelves ends. But Mark assures her that he can take gaps sizes into account as well and he can come up with a satisfactory solution.

The task

Given a shelf length L and a sequence of books B_i, i=1,..,N, where each B_i is of height H_i and width W_i. Let an arrangement of the books on k shelves be represented by a partition of the set \{1,..,N} into sets S₁, S₂, .., S_k where S_i represents indices of books placed on the i-th shelf. Note that, for each i=1,..,k, it must hold |S_i| ≥ 1 and ∑_j∈Si~~ W_j ≤ L, and, for each 1 ≤ i < j ≤ k, every element of S_i is less than any element of S_j. Also note that there is no explicit restriction on the number of shelves k and the shelves depth is large enough to store any of the books.

Let us define cost(S₁,..,S_k)= ∑_i=1,..,k max_j∈Si~~ H_j. This arrangement cost is proportional to the bookcase height, except for shelves thickness which is neglected.

Our task is to find an arrangement of the minimum cost. If there are more such optimal arrangements S₁,..,S_k, we search among them for that one which minimizes maxGap(S₁,..,S_k)=max_i=1,..,k (L-∑_j∈Si~~ W_j). i.e., we minimize the maximum gap at the shelves ends.

To demonstrate efficiency of the optimal solution, we would also like to compare it with a solution obtained by the greedy algorithm. This algorithm creates an arrangement by taking a book by book and placing it onto the current shelf whenever it fits there. If it does not fit, the next shelf becomes the current one and the book is placed there.

Image 1. The image shows books (beige rectangles) arranged on shelves (blue lines except the topmost one which is the upper wall of the bookcase). Each book has a height (the black integer) and a width (the red integer). Hence, the alphabetically ordered sequence of books, where each book is represented by dimensions height×width, is 2×1, 3×1, 5×2, 4×2. The shelf length is L=4. a) Depicts the arrangement created by the greedy algorithm. Its cost is 5+4=9. b) Depicts the only optimal arrangement of cost 3+5=8 and maxGap=2.

Image 2. The alphabetically ordered sequence of books (represented by dimensions heigth×width) is 4×2, 3×2, 11×2, 8×2, 5×2, 3×2, 12×2, 6×1, 12×2, 12×1. The shelf length is L=9. a) Depicts the arrangement created by the greedy algorithm. Its cost is 11+12+12=35. b) Depicts an optimal arrangement of cost 4+11+12=27 and maxGap=7. c) Depicts an optimal arrangement of cost 27 and maxGap=5 which the minimum maxGap value over all optimal arrangements.

Input

The first input line contains two integers, N and L, separated by space. The first integer is the number of books, the second integer is the shelf length. N lines representing books in their alphabetical order follow. An i-th line contains integers H_i and W_i, separated by space.

It holds 1 ≤ N ≤ 6 × 10⁵, 1 ≤ L ≤ 3 × 10⁴. For each i, it holds 1 ≤ H_i ≤ 135, 1 ≤ W_i ≤ 55, and W_i ≤ L.

Output

The output consists of one line containing three integers GC, OC and G, separated by spaces. GC is the cost of the arrangement produced by the greedy algorithm, OC is the cost of an optimal arrangement and G is the minimum value of maxGap(S₁,..,S_k) for an optimal arrangement S₁,..,S_k.

Examples

Example 1

Input

Output

9 8 2

Example 2

Input

Output

35 27 5

Example 3

Input

Output

81 77 2

The data and solution of the first Example are visualized in Image 1, the data and solution of the second Example are visualized in Image 2.

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.

Public data