Find the absent number

Time Limit : 10 Second

Memory Limit : 128 MB

Submission: 235

Solved: 92

Description


Yesterday xiaoY’s teacher HH had given him an interesting problem, and xiaoY got mad about this problem. So he turned to you for help, here is the problem!



HH gave xiaoY a number M and N intervals [xi,yi] which means the integers from xi to yi are all chosen, Now he wanted xiaoY to tell him which number was absent!



(HH ensured that there was just one number absent from 1 to M and any two intervals didn’t overlap)


Input


Multiple cases ended with 2 zeros.



N M (0<N<=10^7, 0<M<=10^8, integer)



N lines followed, each containing two integers:



xi yi  (integer)


Output


An integer (the absent number)


sample input
3 10
3 5
1 2
7 10
2 5
1 2
4 5
0 0
sample output
6
3
hint

since there is too much data, scanf  is recommended.

If you need to use 64bit integer, the following code may be helpful:

#include<iostream>
using namespace std;

int main()
{
    long long a = 12345678987654321LL;
    int b = 88888888, c = 99999999;
    cout << a << endl << (long long)b * c << endl;
    return 0;
}

source
He Jian, HUST Campus 2010, Preliminary
© 2015 HUST ACMICPC TEAM. All Right Reserved.