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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>

int findSchool(const std::vector<std::pair<int64_t, int64_t>> &v, int64_t s) {
  int index = 0;
  for (const auto &[a, b] : v) {
    if (a <= s && s <= b) {
      return index;
    }
    ++index;
  }
  return -1;
}

std::pair<int64_t, int64_t> searchLeft(
    const std::vector<std::pair<int64_t, int64_t>> &v, int64_t s, int index) {
  while (index > 0) {
    if (v[index - 1].second != v[index].first - 1) {
      return {v[index].first - 1, s - (v[index].first - 1)};
    }
    index--;
  }
  if (v[0].first != 1) {
    return {v[0].first - 1, s - (v[0].first - 1)};
  }
  return {-1, std::numeric_limits<int64_t>::max()};
}

std::pair<int64_t, int64_t> searchRight(
    const std::vector<std::pair<int64_t, int64_t>> &v, int64_t s, int64_t n,
    int index) {
  while (index < int(v.size() - 1)) {
    if (v[index].second != v[index + 1].first - 1) {
      return {v[index].second + 1, (v[index].second + 1) - s};
    }
    index++;
  }
  if (v[v.size() - 1].second != n) {
    return {v[v.size() - 1].second + 1, (v[v.size() - 1].second + 1) - s};
  }
  return {-1, std::numeric_limits<int64_t>::max()};
}

int main() {
  int64_t n, m, s;
  std::cin >> n;
  std::cin >> m;
  std::cin >> s;

  std::vector<std::pair<int64_t, int64_t>> v;
  v.reserve(m);

  for (int i = 0; i < m; ++i) {
    int64_t a, b;
    std::cin >> a;
    std::cin >> b;
    v.push_back(std::make_pair(a, b));
  }

  std::sort(v.begin(), v.end());

  // DEBUG
  //   for (const auto &[a, b] : v) {
  //     std::cerr << a << " " << b << std::endl;
  //   }

  int schoolIndex = findSchool(v, s);
  const auto [a, b] = searchLeft(v, s, schoolIndex);
  const auto [c, d] = searchRight(v, s, n, schoolIndex);

  // DEBUG
  //    std::cerr << "index: " << schoolIndex << std::endl;
  //    std::cerr << a << " " << b << " " << c << " " << d << std::endl;

  int64_t result;
  if (a != -1 && c != -1) {
    result = b <= d ? a : c;
  } else {
    result = std::max(a, c);
  }

  std::cout << result << std::endl;
  return 0;
}