Vasya 和 Petya 正在玩在线游戏。和大多数网络游戏一样,它有英雄进度系统,可以让玩家获得经验,使他们的英雄变得更强。瓦夏当然希望获得尽可能多的经验值。仔细研究了经验值分配后,他发现如果自己一个人玩游戏的话,每秒都会获得一点经验值。然而,如果两个玩家一起玩,并且他们当前的经验值最多相差C点,他们可以提升进度,每人每秒获得2点经验值。
由于 Vasya 和 Petya 是中学生,他们的父母不允许他们整天玩耍。每个朋友都有自己的时间表:Vasya 只能在间隔 [a1;b1]、[a2;b2]、...、[an;bn] 期间玩,Petya 只能在间隔 [c1;d1]、[c2;d2]、...、[cm;dm] 期间玩。所有时间段均以从当前时刻开始的秒数给出。 Vasya的数学很好,所以他发现有时候不单独玩也能赚钱,因为经验差异可能会太大,即使一起玩也不会提高进度。
现在他们希望制定这样的比赛时间表,使 Vasya 的最终体验尽可能好。目前玩家的体验也是如此。 Petya并不太关心他的经验,所以他准备在需要的时候配合和发挥,以最大限度地发挥Vasya的经验。
输入
输入数据的第一行包含整数 n、m 和 C — Vasya 可以玩的区间数、Petya 可以玩的区间数以及一起玩时经验水平的最大差异仍然会带来进度提升 (1 ≤ n, m ≤ 2·105, 0 ≤ C ≤ 1018)。
以下 n 行每行包含两个整数:ai、bi - Vasya 可以演奏的时间间隔(0 ≤ ai < bi ≤ 1018,bi < ai + 1)。
以下 m 行每行包含两个整数:ci、di - Petya 可以演奏的时间间隔(0 ≤ ci < di ≤ 1018,di < ci + 1)。
输出
输出一个整数——如果双方玩家都尝试最大化该值,则 Vasya 最终可以获得的最大经验值。
示例
输入 #1
2 1 5 1 7 10 20 10 20
输出 #1
25
输入 #2
1 2 5 0 100 20 60 85 90
输出 #2
125