Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. To Play or not to Play

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya and Petya are playing an online game. As most online games, it has hero progress system that allows players to gain experience that make their heroes stronger. Of course, Vasya would like to get as many experience points as possible. After careful study of experience points allocation, he found out that if he plays the game alone, he gets one experience point each second. However, if two players are playing together, and their current experience values differ by at most *C* points, they can boost their progress, and each of them gets 2 experience points each second.

Since Vasya and Petya are middle school students, their parents don't allow them to play all the day around. Each of the friends has his own schedule: Vasya can only play during intervals [*a*_{1};*b*_{1}], [*a*_{2};*b*_{2}], ..., [*a*_{n};*b*_{n}], and Petya can only play during intervals [*c*_{1};*d*_{1}], [*c*_{2};*d*_{2}], ..., [*c*_{m};*d*_{m}]. All time periods are given in seconds from the current moment. Vasya is good in math, so he has noticed that sometimes it can be profitable not to play alone, because experience difference could become too big, and progress would not be boosted even when played together.

Now they would like to create such schedule of playing that Vasya's final experience was greatest possible. The current players experience is the same. Petya is not so concerned about his experience, so he is ready to cooperate and play when needed to maximize Vasya's experience.

Input

The first line of input data contains integers *n*, *m* and *C* — the number of intervals when Vasya can play, the number of intervals when Petya can play, and the maximal difference in experience level when playing together still gives a progress boost (1 ≤ *n*, *m* ≤ 2·10^{5}, 0 ≤ *C* ≤ 10^{18}).

The following *n* lines contain two integers each: *a*_{i}, *b*_{i} — intervals when Vasya can play (0 ≤ *a*_{i} < *b*_{i} ≤ 10^{18}, *b*_{i} < *a*_{i + 1}).

The following *m* lines contain two integers each: *c*_{i}, *d*_{i} — intervals when Petya can play (0 ≤ *c*_{i} < *d*_{i} ≤ 10^{18}, *d*_{i} < *c*_{i + 1}).

Output

Output one integer — the maximal experience that Vasya can have in the end, if both players try to maximize this value.

Examples

Input

2 1 5

1 7

10 20

10 20

Output

25

Input

1 2 5

0 100

20 60

85 90

Output

125

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/19/2018 05:17:42 (f1).

Desktop version, switch to mobile version.

User lists

Name |
---|