Trip to New York

After the lifting of COVID-19 restrictions, Miltos the dolphin decided to treat himself to a leisure trip to the beautiful New York City and admire some of the most impressive and historic skyscrapers in the world. The time has come for the trip, and his only luggage will be his swimsuit and his camera.

New York City is famous for its "skyscraper skyline." In this problem, we will consider that the skyline consists of N skyscrapers located next to each other in a line, each with a different height H~\mathbf{_i}~ and width W~\mathbf{_i}~.

Miltos wants to photograph the skyline in a way that captures all the skyscrapers (each one entirely) in one or more photos. Each photo he takes can cover a portion of the skyline with a width L. Obviously, each photo must accommodate the tallest skyscraper in the corresponding section. When printing the photos, Miltos cannot change the width, but he can choose paper of the appropriate height to fit the tallest skyscraper.

Help Miltos save as much paper as possible in the printing process. Assist him in finding the way to take photos to minimize the total sum of the heights of the tallest skyscrapers in each photo.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that, after reading the values of N and L, as well as the heights and widths of N skyscrapers, answers the above question.

Input File:

The input file named nytrip.in is a text file. The first line contains two natural numbers separated by a space: the number N of skyscrapers and the width L covered by each photo. Each of the next N lines contains two natural numbers H~\mathbf{_i}~ and W~\mathbf{_i}~, separated by a space: the height and width of the i-th skyscraper.

Output File:

The output file named nytrip.out is a text file that contains exactly one number: the minimum possible sum of the heights of the tallest skyscrapers in each photo.

Examples of input - output files:

STDIN (nytrip.in)

5 10
5 7
9 2
8 5
13 2
3 8

STDOUT (nytrip.out)

21

Explanation: We have N = 5 skyscrapers, and each photo covers a width L = 10. The minimum possible sum of the heights of the tallest skyscrapers from each photo is achieved by taking 3 photos. The first photo will contain only the first skyscraper (5, 7). The second will contain the next three: (9, 2), (8, 5), (13, 2). The third will contain only the last one (3, 8). The sum of the heights of the tallest skyscrapers in each photo is 5+13+3=21.

Constraints:

• 1 ~\le~ N ~\le~ 1.000.000, 1 ~\le~ L ~\le~ 1.000.000.000
• 1 ~\le~ H~_i~ ~\le~ 1.000.000
• 1 ~\le~ W~_i~ ~\le~ 1.000.000 and W~_i~ ~\le~ L
• For test cases with a total value of 11%, 1 ~\le~ N ~\le~ 25
• For test cases with a total value of 23%, 1 ~\le~ N ~\le~ 1000
• For test cases with a total value of 41%, 1 ~\le~ N ~\le~ 30.000

Attention! Be sure to read the input and print the output efficiently, especially if you are programming in C++ or Java. Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 128 MB.