게임을 할 것인가, 말 것인가

Vasya와 Petya는 온라인 게임을 하고 있다. 대부분의 온라인 게임과 마찬가지로 이 게임에도 경험치로 영웅을 강하게 키우는 성장 시스템이 있다. Vasya는 가능한 한 많은 경험치를 얻고 싶어 한다. 혼자 플레이하면 1초마다 경험치를 1 얻는다. 다만 두 사람이 함께 플레이하고 현재 경험치 차이가 $C$ 이하이면 진행이 가속되어, 두 사람 모두 1초마다 경험치를 2씩 얻는다.

Vasya와 Petya는 중학생이라 부모님이 하루 종일 게임하도록 허락하지 않는다. Vasya는 $[a_1, b_1], [a_2, b_2], \ldots, [a_n, b_n]$ 구간에서만 플레이할 수 있고, Petya는 $[c_1, d_1], [c_2, d_2], \ldots, [c_m, d_m]$ 구간에서만 플레이할 수 있다. 모든 시각은 지금 이 순간부터 흐른 초 단위로 주어진다.

Vasya는 수학을 잘한다. 그래서 경험치 차이가 지나치게 커져서 함께 플레이해도 가속이 붙지 않는 경우에는, 혼자 플레이하지 않는 편이 이득일 수도 있다는 점을 알아챘다.

두 사람은 Vasya의 최종 경험치가 최대가 되도록 일정을 짜려고 한다. 처음 두 사람의 경험치는 같다. Petya는 자기 경험치에는 크게 신경 쓰지 않으므로, Vasya의 경험치를 최대로 만드는 데 필요하다면 기꺼이 함께 플레이해 준다.

첫째 줄에 정수 $n$, $m$, $C$가 주어진다. $n$은 Vasya가 플레이할 수 있는 구간의 수, $m$은 Petya가 플레이할 수 있는 구간의 수, $C$는 함께 플레이할 때 가속이 적용되는 최대 경험치 차이이다 ($1 \le n, m \le 2 \cdot 10^5$, $0 \le C \le 10^{18}$).

다음 $n$개 줄에는 Vasya가 플레이할 수 있는 구간 $a_i$, $b_i$가 각각 주어진다 ($0 \le a_i < b_i \le 10^{18}$, $b_i < a_i + 1$).

그다음 $m$개 줄에는 Petya가 플레이할 수 있는 구간 $c_i$, $d_i$가 각각 주어진다 ($0 \le c_i < d_i \le 10^{18}$, $d_i < c_i + 1$).

두 사람이 이 값을 최대화하려 할 때, Vasya가 최종적으로 가질 수 있는 경험치의 최댓값을 정수 하나로 출력한다.