When you go out from the toilet to go back to class you discover that a group of velociraptors has entered to the classroms and has devoured your classmates. The corridor where you are is closed: running away is impossible. Velociraptors, inside the classroms digesting, will go out at any moment to finish with you. Oh, well! It is known that this kind of things happen sometimes.

The corridor of your high school is represented by a segment of the real line from 0 to 2n−2, with n doors of n classroms, placed over the points 0, 2, 4, …, 2n−2 of the line. The toilet where you are going out from is placed at the point k with 0≤ k ≤ 2n−2 and even k. You as well as the velociraptors take 1 second to cover a distance unit over the line (velociraptors are already satisfied and they are not going to run for a miserable desert).

You are asked to, assuming that you know which velociraptors will go out
from the classroms to devour you and the moments of time t_{i} that they will do it, and
also assuming that these ones will head for you (wherever you are)
as soon as they go out, say how many seconds you can extend your (brief but intense)
life time making the right movements.

[r]

We consider that will be very useful to think in space-time diagrams as the one on the right, where it is illustrated a possible situaton for k=6 and n=11, where 3 velociraptors go out from the classroms placed in the points 2, 4 and 14 at the moments 6, 10 and 8 respectively. The correct answer to this case is 13.

Input

A test data contains various cases. Each case starts with three
naturals n, m and k, with 0≤ k≤ 2n−2, 1≤ n≤ 10^{8} and
1≤ m ≤ 10000, where n and k are as it is describe in the
wording and m is the number of velociraptors. The next m lines
of the input contain a pair of numbers c_{i}, t_{i}, where c_{i} is the classroom
that has devoured the i-th velociraptor and t_{i} is the moment of
time that it will go out for its desert. It is fulfilled that
0≤ a_{i}≤ 2n−2 and 0≤ t_{i}≤ 10^{9} for any i, that c_{i} and
t_{i} are even, and that all the c_{i} are different.

Output

For each case, your program must print in a line the time that you
can extend your life. As times t_{i} and classrooms are even numbers
it is fulfilled that the answer will always be an integer.

Scoring

- Test1: 45 Points
Test data with no more than 20 cases with n=m ≤ 100 and where the c

_{i}appear sorted (as in the instance 1).

- Test2: 30 Points
Test data with no more than 20 cases with n≤ 1000 and m≤ 100 (as in the instances 2 and 3).

- Test3: 25 Points
Test data with no more than 20 cases of n≤ 10

^{8}and m≤ 10^{4}(as in the instance 4).

Public test cases

**Input**

5 5 4 0 0 2 2 4 4 6 2 8 0 5 5 4 0 0 2 2 4 6 6 2 8 0 5 5 4 0 0 2 6 4 6 6 6 8 0 5 5 4 0 20 2 2 4 20 6 20 8 20 5 5 4 0 2 2 20 4 20 6 20 8 0 5 5 4 0 2 2 4 4 0 6 2 8 2 5 5 0 0 2 2 0 4 10 6 10 8 10 3 3 2 0 10 2 10 4 10

**Output**

4 4 4 8 5 0 2 11

**Input**

11 3 6 2 6 4 10 14 8

**Output**

13

**Input**

1000 1 0 100 100 1000 1 0 100 98 540 5 482 508 1064 392 286 472 338 186 818 62 840 43 2 0 24 72 44 44 90 7 18 68 112 34 84 8 16 82 82 24 60 52 152 36 28

**Output**

200 198 944 88 170

**Input**

50000000 7 67958422 87401816 62889408 6968110 151700716 72342116 155469888 89165870 73851810 94055040 7972090 34446444 32438808 11204152 4411784 50000000 10 54159472 16811258 75071762 82396964 125722710 45739798 94247702 8034262 18999860 36992544 92063428 87918930 66633664 82468966 168041758 40581626 31570418 50437158 161755152 19037120 148790458

**Output**

47617381 78714732

Information

- Author
- Omer Giménez
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++