To Play or not to Play

## 题目描述 Vasya和Petya在玩一个网络游戏。这个游戏有一个英雄成长系统，可以通过涨经验值让玩家的英雄变强。Vasya当然想获得尽可能多的经验值。经过研究，Vasya发现如果他一个人玩，他每秒钟可以得到1点经验值；但是如果两个人一起玩，并且两人的经验值之差（的绝对值）不超过$C$，他们每秒都可以得到2点经验值。 因为Vasya和Petya是初中生，他们的家长不允许他们一天都在打游戏。Vasya可以在$n$个不重叠的时间区间内$[a_1,b_1],[a_2,b_2],\cdots ,[a_n,b_n]$上线，Petya可以在$m$个不重叠的时间区间内$[c_1,d_1],[c_2,d_2],\cdots ,[c_m,c_m]$上线。Vasya注意到有时候只一个人玩会比两个人一起玩更优，因为两人的经验值差距太大的话，经验值不会加速增长。 现在Vasya和Petya想要制定一个计划表，让Vasya的最终经验值最大。当前两人的经验值相同。Petya不在意自己的经验值，他会全力配合Vasya，使Vasya的经验值最大。 ## 输入格式 第一行包含3个正整数$n,m,C(1 \le n,m \le 2 \cdot 10^5 , 0 \le C \le 10^{18}) $，为Vasya可以上线的时间段数量、Petya可以上线的时间段数量、可以加速涨分的最大分差$C$。 接下来$n$行，每行包含2个整数$a_i,b_i(0 \le a_i,b_i \le 10^{18},b_i < a_i+1)$ 接下来$m$行，每行包含2个整数$c_i,d_i(0 \le c_i,d_i \le 10^{18},d_i < c_i+1)$ ## 输出格式 一个整数，Vasya可能获得的最大经验值

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.

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}&lt;b_{i}<=10^{18} $ , $ b_{i}&lt;a_{i+1} $ ). The following $ m $ lines contain two integers each: $ c_{i},d_{i} $ — intervals when Petya can play ( $ 0<=c_{i}&lt;d_{i}<=10^{18} $ , $ d_{i}&lt;c_{i+1} $ ).

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

2 1 5
1 7
10 20
10 20

25

1 2 5
0 100
20 60
85 90

125