1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <iomanip>
#include <algorithm>

//#define DEBUG

#ifdef DEBUG
    #undef DEBUG
    #define DEBUG(x) x
#else
    #define DEBUG(x)
#endif

using namespace std;

#define MAX_M 1003
#define REP(x,n) for(int x=0;x<(n);++x)

typedef pair<long long, long long> Range;
Range unavailableRanges[MAX_M];

ostream& operator<<(ostream& os, const Range& r) {
    return os << "(" << r.first << ", " << r.second << ")";
}

long long solve(int m, long long s) {
    sort(unavailableRanges, unavailableRanges+m, [](const Range& a, const Range& b) {return a.first < b.first;});
    DEBUG(REP(x,m) {
        cerr << unavailableRanges[x] << endl;
    })
    
    int startIndex=0;
    for(;unavailableRanges[startIndex].second < s; ++startIndex);
    DEBUG(cerr << "s ("<<s<<") found in range "<<startIndex<<" "<<unavailableRanges[startIndex]<<endl;)
    long long nearestLower = -1000000000000000LL, nearestHigher = 1000000000000000LL;
    for (int i=startIndex; i>0; --i) {
        if (unavailableRanges[i].first - unavailableRanges[i-1].second > 1) {
            nearestLower = unavailableRanges[i].first - 1;
            break;
        }
    }
    for (int i=startIndex; i<m-1; ++i) {
        if (unavailableRanges[i+1].first - unavailableRanges[i].second > 1) {
            nearestHigher = unavailableRanges[i].second + 1;
            break;
        }
    }
    DEBUG(cerr<<"lower = "<<nearestLower << ", higher="<<nearestHigher<<endl;)
    if (nearestHigher-s < s-nearestLower) {
        return nearestHigher;
    } else {
        return nearestLower;
    }

}

int main() {
    ios_base::sync_with_stdio(0);
    long long n,s;
    int m;
    cin >> n >> m >> s;
    REP(x,m)
        cin >> unavailableRanges[x].first >> unavailableRanges[x].second;
    unavailableRanges[m+1].first = unavailableRanges[m+1].second = n+1;
    unavailableRanges[m+2].first = unavailableRanges[m+2].second = 0;

    cout << solve(m+2, s) << endl;
    return 0;
}