Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Играть или не играть
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася и Петя играют в онлайн-игру. Как и во многих онлайн-играх, в этой есть своя схема прокачки, которая заключается в том, что чем больше опыта получил персонаж, тем он сильнее. Конечно, Вася хочет как можно быстрее получить максимальное количество опыта. Внимательно изучив правила игры, Вася понял, что если человек играет в игру один, то он получает одну единицу опыта каждую секунду, пока играет. Но если два игрока играют в одно время, и их текущий опыт отличается не больше, чем на число C, то они могут играть в команде, и тогда каждый из них будет получать по 2 единицы опыта в секунду.

Поскольку Вася и Петя еще учатся в школе, их родители не разрешают им играть круглые сутки, так что у каждого из друзей есть свое расписание: Вася может играть в какие-то промежутки времени [a1;b1], [a2;b2], ..., [an;bn], а Петя в [c1;d1], [c2;d2], ..., [cm;dm] (все промежутки рассчитаны точно в секундах от текущего момента). Наблюдательный Вася, успевающий в математике, заметил, что иногда может быть выгодно не играть, чтобы не сильно оторваться в полученном опыте от своего друга, и, когда он зайдет в сеть, играть вдвоем, получая больше опыта.

Помогите ребятам составить такое расписание для игры, чтобы в итоге Вася получил как можно больше опыта. Сейчас у их персонажей одинаковое количество набранного опыта. Считайте, что Петя готов скооперироваться с Васей и играть тогда, когда тот скажет, чтобы помочь Васе достичь максимального количества опыта.

Входные данные

В первой строке даны три целых числа n, m, C — количество непрерывных отрезков времени, в которые могут играть Вася и Петя, и максимальная допустимая разница опыта для удвоенного получения опыта, соответственно (1 ≤ n, m ≤ 2·105, 0 ≤ C ≤ 1018).

В следующих n строках дано по два числа ai, bi — промежутки времени, в которые может играть Вася (0 ≤ ai < bi ≤ 1018, bi < ai + 1).

В следующих m строках дано по два числа ci, di — промежутки времени, в которые может играть Петя (0 ≤ ci < di ≤ 1018, di < ci + 1).

Выходные данные

Выведите одно целое число — максимальное значение полученного опыта, которое может достичь Вася при правильной игре.

Примеры
Входные данные
2 1 5
1 7
10 20
10 20
Выходные данные
25
Входные данные
1 2 5
0 100
20 60
85 90
Выходные данные
125