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 [a1;b1], [a2;b2], ..., [an;bn], and Petya can only play during intervals [c1;d1], [c2;d2], ..., [cm;dm]. 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.

Input

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: ai, bi — intervals when Vasya can play (0 ≤ ai < bi ≤ 1018, bi < ai + 1).

The following m lines contain two integers each: ci, di — intervals when Petya can play (0 ≤ ci < di ≤ 1018, di < ci + 1).

Output

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

Examples

Input

2 1 5
1 7
10 20
10 20


Output

25


Input

1 2 5
0 100
20 60
85 90


Output

125
#include <bits/stdc++.h>
using namespace std;
const int N = 800050;
const long long inf = 9e18;
mt19937 rng(time(0));
int ls[N], rs[N], tsz, root, pri[N];
long long x[N], y[N], lzy_x[N], lzy_y[N], my[N], ms[N], ss[N], se[N];
void pull(int c) {
  ss[c] = se[c] = x[c];
  if (ls[c]) ss[c] = ss[ls[c]];
  if (rs[c]) se[c] = se[rs[c]];
  my[c] = max({my[ls[c]], my[rs[c]], y[c]});
  ms[c] = max({ms[ls[c]], ms[rs[c]], y[c] - x[c]});
}
void upd(int c, long long ax, long long ay) {
  x[c] += ax;
  y[c] += ay;
  ss[c] += ax;
  se[c] += ax;
  my[c] += ay;
  ms[c] += ay - ax;
  lzy_x[c] += ax;
  lzy_y[c] += ay;
}
void push(int c) {
  if (lzy_x[c] == 0 && lzy_y[c] == 0) return;
  if (ls[c]) upd(ls[c], lzy_x[c], lzy_y[c]);
  if (rs[c]) upd(rs[c], lzy_x[c], lzy_y[c]);
  lzy_x[c] = lzy_y[c] = 0;
}
int make(long long x, long long y, long long s) {
  ++tsz;
  pri[tsz] = rng();
  ::x[tsz] = x;
  ::y[tsz] = max(y, s + x);
  pull(tsz);
  return tsz;
}
void rot_l(int& c) {
  int a = rs[c], b = ls[a];
  rs[c] = b;
  ls[a] = c;
  pull(c);
  pull(a);
  c = a;
}
void rot_r(int& c) {
  int a = ls[c], b = rs[a];
  ls[c] = b;
  rs[a] = c;
  pull(c);
  pull(a);
  c = a;
}
void ins(int& c, long long x, long long y, long long s) {
  if (!c)
    c = make(x, y, s);
  else {
    push(c);
    if (::x[c] == x) {
      ::y[c] = max({::y[c], max(y, my[ls[c]]), max(s, ms[rs[c]]) + x});
      pull(c);
    } else if (::x[c] < x) {
      ins(rs[c], x, max({y, my[ls[c]], ::y[c]}), s);
      if (pri[rs[c]] > pri[c])
        rot_l(c);
      else
        pull(c);
    } else {
      ins(ls[c], x, y, max({s, ms[rs[c]], ::y[c] - ::x[c]}));
      if (pri[ls[c]] > pri[c])
        rot_r(c);
      else
        pull(c);
    }
  }
}
void add(int c, long long qs, long long qe, long long ay) {
  if (!c || ss[c] > qe || qs > se[c]) return;
  if (qs <= ss[c] && qe >= se[c])
    upd(c, 0, ay);
  else {
    push(c);
    if (::x[c] >= qs && ::x[c] <= qe) ::y[c] += ay;
    add(ls[c], qs, qe, ay);
    add(rs[c], qs, qe, ay);
    pull(c);
  }
}
int main() {
  my[0] = ms[0] = -inf;
  int n, m;
  long long C;
  scanf("%i %i %lld", &n, &m, &C);
  vector<pair<long long, int>> evs;
  for (int i = 1; i <= 2 * n; i++) {
    long long x;
    scanf("%lld", &x);
    evs.push_back({x, 1});
  }
  for (int i = 1; i <= 2 * m; i++) {
    long long x;
    scanf("%lld", &x);
    evs.push_back({x, 2});
  }
  sort(evs.begin(), evs.end());
  root = make(0, 0, 0);
  for (int i = 1, mask = evs[0].second; i < evs.size(); i++) {
    long long t = evs[i].first - evs[i - 1].first;
    if (mask & 1) upd(root, t, t);
    if (mask & 2) upd(root, -t, 0);
    if (mask == 3) {
      ins(root, -C, -inf, -inf);
      ins(root, C, -inf, -inf);
      add(root, -C, C, t);
    }
    mask ^= evs[i].second;
  }
  printf("%lld\n", my[root]);
  return 0;
}
