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;
unsigned int las = 2333333;
int n, m, t;
long long C, add;
struct eve {
  long long x;
  int t;
} a[800100];
bool cmp(eve a, eve b) { return a.x < b.x; }
void read(long long& n) {
  n = 0;
  char c;
  for (; (c = getchar()) < 48 || c > 57;)
    ;
  for (; c > 47 && c < 58; c = getchar()) n = n * 10 + c - 48;
}
unsigned int nw() {
  las ^= las << 4;
  las ^= las << 8;
  las ^= las >> 5;
  las ^= las >> 10;
  return las;
}
struct treap {
  treap *l, *r;
  long long x, y, adx, ady;
  unsigned int key;
  treap(long long _x = 0, long long _y = 0) {
    adx = ady = 0;
    x = _x;
    y = _y;
    key = nw();
    l = r = 0;
  }
  void upd(long long u, long long v) {
    adx += u;
    x += u;
    ady += v;
    y += v;
  }
  void down() {
    if (!adx && !ady) return;
    if (l) l->upd(adx, ady);
    if (r) r->upd(adx, ady);
    adx = ady = 0;
  }
};
void lturn(treap* x) {
  treap* y = x->r;
  x->r = y->l;
  y->l = x;
  x = y;
}
void rturn(treap* x) {
  treap* y = x->l;
  x->l = y->r;
  y->r = x;
  x = y;
}
treap* merge(treap* a, treap* b) {
  if (!a || !b) return a ? a : b;
  if (a->key < b->key) {
    a->down();
    a->r = merge(a->r, b);
    return a;
  }
  b->down();
  b->l = merge(a, b->l);
  return b;
}
void split(treap* a, long long L, treap*& lf, treap*& rg) {
  if (!a) {
    lf = rg = 0;
    return;
  }
  a->down();
  if (a->x - a->y >= L)
    rg = a, split(a->l, L, lf, rg->l);
  else
    lf = a, split(a->r, L, lf->r, rg);
}
treap* left(treap* a) {
  if (!a) return 0;
  a->down();
  if (!a->l) return a;
  return left(a->l);
}
treap* right(treap* a) {
  if (!a) return 0;
  a->down();
  if (!a->r) return a;
  return right(a->r);
}
void del(treap*& a) {
  a->down();
  if (!a->l)
    a = a->r;
  else
    del(a->l);
}
void der(treap*& a) {
  a->down();
  if (!a->r)
    a = a->l;
  else
    der(a->r);
}
int main() {
  cin >> n >> m >> C;
  for (int i = 1; i <= n + n; ++i) read(a[++t].x), a[t].t = 1;
  for (int i = 1; i <= m + m; ++i) read(a[++t].x), a[t].t = 2;
  sort(a + 1, a + t + 1, cmp);
  int st = 0;
  treap* root = new treap(0, 0);
  for (int i = 1; i < t; ++i) {
    st ^= a[i].t;
    if (!st) continue;
    long long T = a[i + 1].x - a[i].x;
    if (!T) continue;
    if (st == 1)
      root->upd(T, 0);
    else if (st == 2)
      root->upd(0, T);
    else {
      add += T;
      treap *t1 = 0, *t2 = 0, *t3 = 0;
      split(root, -C, t1, t2);
      split(t2, C, t2, t3);
      long long rx = 0, ry = -C, lx = -C, ly = 0;
      if (t1) {
        lx = (right(t1))->x;
        ly = lx + C;
      }
      if (t3) {
        ry = (left(t3))->y;
        rx = ry + C;
      }
      if (lx > rx || ly > ry) {
        treap* L = new treap(lx, ly);
        if (!t2)
          t2 = L;
        else {
          treap* tmp = left(t2);
          if (lx > tmp->x || ly > tmp->y) t2 = merge(L, t2);
        }
      }
      if (rx > lx || ry > ly || (rx == lx && ry == ly)) {
        treap* R = new treap(rx, ry);
        if (!t2)
          t2 = R;
        else {
          treap* tmp = right(t2);
          if (rx > tmp->x || ry > tmp->y) t2 = merge(t2, R);
        }
      }
      t2->upd(T, T);
      treap *l = left(t2), *r = right(t2);
      while (t1) {
        treap* tmp = right(t1);
        if (tmp->x <= l->x && tmp->y <= l->y)
          der(t1);
        else
          break;
      }
      while (t3) {
        treap* tmp = left(t3);
        if (tmp->x <= r->x && tmp->y <= r->y)
          del(t3);
        else
          break;
      }
      root = merge(merge(t1, t2), t3);
    }
  }
  cout << add + (right(root))->x;
}
