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