Problem Description

Lovely Village has only one long street extending from east to west, with $m$ houses. Each house has a unique house number, starting from $1$ to $m$.

A recent blizzard destroyed most of the telephone lines, so the mayor funded the construction of a new telephone network. Mirko is interested in the popularity of this new telephone network, so he installed special detectors at some points.

These detectors can detect any call between two houses, one house to the east of the detector and one house to the west of the detector.

At the end of the first month, Mirko removed all the detectors and now wants to know the minimum number of calls that could have been made during this month.

Input Format

The first line contains two positive integers, $n$ and $m$, representing the number of detectors and houses, respectively.

The next $n$ lines each contain two positive integers $P_i$ and $C_i$, where $P_i$ is the position of the detector and $C_i$ is the total number of calls detected by the detector with number $i$. We say a detector is at position $P_i$ if and only if it is between house number $P_i$ and house number $P_i+1$.

There is at most one detector at any given position.

Output Format

Output a single positive integer, representing the minimum number of calls.

Sample Input and Output

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

Notes

Data Size and Constraints

• For $50\%$ of the data, $1 \le n \le 10^3$, $1 \le C_i \le 10^3$, $n < m \le 10^9$, $1 \le P_i < m$.
• For $100\%$ of the data, $1 \le n \le 10^5$, $1 \le C_i \le 10^9$, $n < m \le 10^9$, $1 \le P_i < m$.

Notes

Translated from COCI 2009-2010 #3 T4 RAZGOVOR, full score is 100, each test case is worth 10 points, with a total of 10 test cases.

见题面 Input 部分

见题面 Output 部分