CF856F.To Play or not to Play

Vasya 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.

瓦西娅和佩佳正在玩一款在线游戏。和大多数在线游戏一样，该游戏拥有英雄成长系统，玩家可以通过获取经验值来提升英雄实力。当然，瓦西娅希望尽可能多地获得经验值。经过对经验值分配机制的仔细研究，他发现：如果他独自玩游戏，每秒可获得 1 点经验值；但如果两名玩家一起游戏，且他们当前的经验值之差至多为 $C$ 点，则他们的成长进度可以得到“增益”，此时每人每秒均可获得 2 点经验值。

由于瓦西娅和佩佳都是中学生，他们的父母不允许他们全天候玩游戏。每位朋友都有各自的游戏时间安排：瓦西娅只能在区间 $[a_1;b_1],\ [a_2;b_2],\ \dots,\ [a_n;b_n]$ 内玩游戏，佩佳只能在区间 $[c_1;d_1],\ [c_2;d_2],\ \dots,\ [c_m;d_m]$ 内玩游戏。所有时间段均以当前时刻起算的秒数给出。瓦西娅数学很好，因此他注意到：有时不独自游戏反而更有利，因为若独自游戏过久，双方经验差可能变得过大，导致即使之后一同游戏也无法触发增益效果。

现在，他们希望制定一个最优的游戏时间安排，使得瓦西娅最终获得的经验值最大化。初始时，两名玩家的经验值相同。佩佳并不太在意自己的经验值，因此他愿意全力配合——在必要时进行游戏，以使瓦西娅的经验值最大化。

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·105, 0 ≤ C ≤ 1018).

The following n lines contain two integers each: a__i, b__i — intervals when Vasya can play (0 ≤ a__i < b__i ≤ 1018, 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 ≤ 1018, d__i < c__i + 1).

输入数据的第一行包含三个整数 $n$、$m$ 和 $C$ —— 分别表示瓦夏可玩游戏的时间段数量、佩佳可玩游戏的时间段数量，以及两人共同游戏时仍能获得经验提升的最大经验等级差（$1 \leq n, m \leq 2 \cdot 10^5$，$0 \leq C \leq 10^{18}$）。

接下来的 $n$ 行每行包含两个整数：$a_i$、$b_i$ —— 表示瓦夏可玩游戏的时间段（$0 \leq a_i < b_i \leq 10^{18}$，且 $b_i < a_{i+1}$）。

接下来的 $m$ 行每行包含两个整数：$c_i$、$d_i$ —— 表示佩佳可玩游戏的时间段（$0 \leq c_i < d_i \leq 10^{18}$，且 $d_i < c_{i+1}$）。

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

输出一个整数——即在双方玩家均试图最大化该值的情况下，瓦西娅最终所能获得的最大经验值。