COCI '09 Contest 3 #4 Razgovori

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

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.

Recent storm took out most phone lines so the mayor financed 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.

Detector detects any phone call made between two houses, as long as one of them is eastward and the other 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 Specification

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

Next N lines contains two numbers each: P_i (1 \le P_i < M), and C_i (1 \le C_i \le 1\,000\,000\,000), the position and total number of phone calls detected by detector numbered 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 on the same position.

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

Output Specification

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

Sample Input 1

3 4
3 1
2 2
1 1

Sample Output 1

2

Sample Input 2

2 3
1 23
2 17

Sample Output 2

23

Sample Input 3

3 9
7 2
8 3
3 4

Sample Output 3

5

Comments

There are no comments at the moment.