Description

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

A recent snowstorm destroyed most of the telephone lines, so the mayor funded the construction of a new telephone line network. Mirko is very interested in how widely this new telephone network is used, so he installed special sensors at some positions.

A sensor can detect any phone call between two houses such that one house is to the east of the sensor and the other house is to the west of the sensor.

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

Input Format

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

In the next $n$ lines, each line contains two positive integers $P_i$ and $C_i$, meaning the position and the total number of calls detected by sensor $i$. We say that a sensor is at position $P_i$ if and only if it is placed between house $P_i$ and house $P_i + 1$.

There is at most one sensor at the same position.

Output Format

Output one positive integer, the minimum number of calls.

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

Hint

Constraints

• For $50\%$ of the testdata, $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 testdata, $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 100. Each test point is worth 10 points, with 10 test points in total.

Translated by ChatGPT 5