F. To Play or not to Play

Vasya 和 Petya 正在玩一款在线游戏。和大多数在线游戏一样，该游戏有角色成长系统，玩家可以通过获得经验值来增强他们的角色。当然，Vasya 希望获得尽可能多的经验值。经过仔细研究经验值的分配机制，他发现：如果他独自玩游戏，每秒获得 1 点经验值；但如果两名玩家一起玩，且他们的当前经验值相差不超过 $C$ 点，则可以提升进度，每人每秒获得 2 点经验值。 由于 Vasya 和 Petya 是中学生，他们的父母不允许他们整天玩游戏。每位朋友都有自己的时间表：Vasya 只能在区间 #cf_span[[a1;b1], [a2;b2], ..., [an;bn]] 内玩游戏，Petya 只能在区间 #cf_span[[c1;d1], [c2;d2], ..., [cm;dm]] 内玩游戏。所有时间区间均以当前时刻起的秒数给出。Vasya 数学很好，他注意到，有时独自玩游戏反而更划算，因为经验值差距可能变得过大，即使一起玩也无法获得进度加成。 现在他们希望制定一个游戏计划，使得 Vasya 的最终经验值最大化。初始时两名玩家的经验值相同。Petya 对自己的经验值不太在意，因此他愿意配合，在需要时一起玩以最大化 Vasya 的经验值。 输入数据的第一行包含整数 #cf_span[n], #cf_span[m] 和 #cf_span[C] —— 分别表示 Vasya 可以玩游戏的区间数量、Petya 可以玩游戏的区间数量，以及一起玩时仍能获得进度加成的最大经验值差值（#cf_span[1 ≤ n, m ≤ 2·105], #cf_span[0 ≤ C ≤ 1018]）。 接下来的 #cf_span[n] 行，每行包含两个整数：#cf_span[ai, bi] —— Vasya 可以玩游戏的区间（#cf_span[0 ≤ ai < bi ≤ 1018], #cf_span[bi < ai + 1]）。 接下来的 #cf_span[m] 行，每行包含两个整数：#cf_span[ci, di] —— Petya 可以玩游戏的区间（#cf_span[0 ≤ ci < di ≤ 1018], #cf_span[di < ci + 1]）。 请输出一个整数 —— 在两名玩家都试图最大化 Vasya 的经验值的情况下，Vasya 最终能获得的最大经验值。 ## Input 输入数据的第一行包含整数 #cf_span[n], #cf_span[m] 和 #cf_span[C] —— 分别表示 Vasya 可以玩游戏的区间数量、Petya 可以玩游戏的区间数量，以及一起玩时仍能获得进度加成的最大经验值差值（#cf_span[1 ≤ n, m ≤ 2·105], #cf_span[0 ≤ C ≤ 1018]）。接下来的 #cf_span[n] 行，每行包含两个整数：#cf_span[ai, bi] —— Vasya 可以玩游戏的区间（#cf_span[0 ≤ ai < bi ≤ 1018], #cf_span[bi < ai + 1]）。接下来的 #cf_span[m] 行，每行包含两个整数：#cf_span[ci, di] —— Petya 可以玩游戏的区间（#cf_span[0 ≤ ci < di ≤ 1018], #cf_span[di < ci + 1]）。 ## Output 请输出一个整数 —— 在两名玩家都试图最大化 Vasya 的经验值的情况下，Vasya 最终能获得的最大经验值。 [samples]

**Definitions:** - Let $ V = \bigcup_{i=1}^n [a_i, b_i] $ be the set of time intervals during which Vasya can play. - Let $ P = \bigcup_{j=1}^m [c_j, d_j] $ be the set of time intervals during which Petya can play. - Let $ C \geq 0 $ be the maximum allowable experience difference for a boost when playing together. - Let $ x(t) $ be Vasya’s experience at time $ t $, and $ y(t) $ be Petya’s experience at time $ t $. Initially, $ x(0) = y(0) = 0 $. - At any time $ t $, if both players are playing (i.e., $ t \in V \cap P $) and $ |x(t) - y(t)| \leq C $, then both gain 2 experience points per second. - Otherwise, if only one player is playing, that player gains 1 experience point per second; the other gains 0. **Constraints:** - $ V $ and $ P $ are unions of disjoint, non-overlapping, sorted intervals: $ a_i < b_i < a_{i+1} $, $ c_j < d_j < c_{j+1} $. - Time is continuous and measured in seconds from $ t = 0 $. - Players may choose to play or not play during their available intervals (i.e., they can skip parts of their available time). **Objective:** Maximize $ x(T) $, where $ T $ is the end of the last possible play time (i.e., $ T = \max(\max_i b_i, \max_j d_j) $), under the constraint that Petya cooperates optimally to maximize Vasya’s final experience. **Formal Problem:** Find the maximum possible value of $ x(T) $, given: - $ x(t), y(t) $ are non-decreasing, piecewise linear functions with slopes in $ \{0, 1, 2\} $. - For all $ t \in [0, T] $: - If $ t \in V \setminus P $, then $ \dot{x}(t) = 1 $, $ \dot{y}(t) = 0 $. - If $ t \in P \setminus V $, then $ \dot{x}(t) = 0 $, $ \dot{y}(t) = 1 $. - If $ t \in V \cap P $, then: - If $ |x(t) - y(t)| \leq C $, then $ \dot{x}(t) = \dot{y}(t) = 2 $. - Else, $ \dot{x}(t) = 1 $, $ \dot{y}(t) = 1 $. - Players may choose to **not play** during any subinterval of their available time (i.e., they can skip parts of $ V $ or $ P $). **Goal:** Maximize $ x(T) $ by optimally choosing, for each $ t \in V \cup P $, whether to play or not, subject to the above dynamics and constraints. --- **Note:** Since Petya is cooperative and only aims to maximize Vasya’s experience, he will adjust his play schedule (within his available intervals) to keep $ |x(t) - y(t)| \leq C $ for as long as possible during overlapping intervals, thereby enabling the 2x boost for Vasya. Thus, the problem reduces to: **Maximize total experience gained by Vasya over time, by optimally scheduling play (including skipping parts of available intervals) such that during overlapping intervals, experience difference is kept ≤ C to enable the 2x boost, and otherwise Vasya gains 1 per second when playing alone.**