Problem H
Training
Ashley is training for a programming contest on Brandon’s Online Judge. Brandon’s Online Judge has a new feature which allows Ashley’s coach, Tom, to load a list of problems for Ashley.
Tom has curated some problems for Ashley to work on. Each problem has two integers as a lower skill bound and an upper skill bound. Each programmer has an integer skill level. If someone with a skill level between the lower and upper bounds of a problem (inclusive), and they solve that problem, then his/her skill level goes up by $1$.
Ashley will train on Tom’s curated list of problems as follows – she will look at the first problem on the list and either solve it or skip it. She will repeat this for every problem on the list in the order Tom loaded the problems. Once she has skipped a problem, she can never go back to it.
Compute the maximum skill level Ashley can have if she chooses to solve or skip problems optimally.
Input
The first line contains two integers $n$ and $s$ $(1 \le n \le 10^5, 0 \le s \le 10^9)$, where $n$ is the number of problems Tom has curated for Ashley, and $s$ is Ashley’s current skill level.
Each of the next $n$ lines contains two integers $l$ and $r$ $(0 \le l \le r \le 2 \cdot 10^9)$. These are the lower ($l$) and upper ($r$) skill bounds on each of Tom’s problems, in the order that Tom loaded them.
Output
Output a single integer, which is the maximum skill level Ashley can attain.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 0 0 2 0 0 1 1 |
2 |
