COCI 2009/2010, Contest #3

Task RAZGOVORI

Mirko's village has only one long street stretching from east to west with M houses. Each house has a unique house number, starting with 1 and ending with M.

A recent storm took out most phone lines, so the mayor financed the construction of a new one. Mirko is interested in the popularity of this new phone network, so he infiltrated its construction and placed special detectors on some points.

Detectors detect any phone call made between two houses, as long as one of them is eastward and the other is westward from the point the detector is installed.

At the end of the first month, Mirko removed all detectors and now wonders what is the smallest number of phone calls that could have been made during that month.

Input

The first line of the input contains two integers, N (1 ≤ N ≤ 100 000), the number of detectors, and M (N < M ≤ 1 000 000 000), the number of houses in the village.

The next N lines contain two numbers each: P_i (1 ≤ P_i < M), and C_i (1 ≤ C_i ≤ 1 000 000 000), the position and total number of phone calls detected by detector number i. We say that a detector is on position P_i if and only if he is between houses numbered P_i and P_i+1.

There will never be more than one detector at the same position.

Output

Output a single integer, the minimal number of phone calls made.

Grading

In test cases worth 50% of the points, N and C will be smaller than 1 000.

Sample Tests

3 4
3 1
2 2
1 1

2

2 3
1 23
2 17

23

3 9
7 2
8 3
3 4

5

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Jul 02, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)