P7260 [COCI 2009/2010 #3] RAZGOVOR

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.

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 one positive integer, the minimum number of calls.

#### 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](https://hsin.hr/coci/archive/2009_2010/contest3_tasks.pdf), full score 100. Each test point is worth 10 points, with 10 test points in total. Translated by ChatGPT 5