Задача 13

Бомж Миха и две расчёски

Бомж Миха, несмотря на низкий социальный статус, тщательно следит за своим имиджем. Он является счастливым обладателем расчёски (рисунок 1). Когда-то в расчёске было N₁ зубчиков, но Михе она досталась уже изрядно покоцанной: в ней M₁ последовательностей целых зубчиков, для каждой известны номер начального зубчика A_{1, i} и номер конечного зубчика B_{1, i}, i = 1..M₁.

Вы, очевидно, уже догадались (по цифре 1 в идентификаторах), что Миха нашёл ещё одну расчёску с теми же размерами зубчиков. Про неё известно всё то же, что про первую, только с цифрой 2 в идентификаторах (N₂, M₂, …). И вы уже поняли, что Миха намерен склеить две расчёски, чтобы получить одну полноценную, без дыр и максимально возможной длины. При этом размер накладывающихся друг на друга частей расчёсок должен быть не меньше половины длины меньшей из расчёсок, чтобы склеенная расчёска выдержала прохождение через космы Михи. Требуется написать программу для определения максимальной длины расчёски.

Если целая расчёска не собирается, программа должна выводить 0.

Ввод
Первая строка содержит числа N₁, M₁, N₂, M₂, разделённые пробелами.
Во второй строке находится M₁ пар чисел A_{1, I}, B_{1, I}, разделённых пробелами. Аналогично для третьей строки, содержащей M₂ пар чисел A_{2, I}, B_{2, I}.

Вывод
Требуется вывести число – максимальную длину расчёски.

Пример ввода                                                    Консольный вывод

4 2 4 1 1 2 4 4 3 3

4

Описание примера: