Противостояние

Неожиданно для всех между Волантисом и Пентосом разразилась война. Жители Волантиса, зная, что вот-вот будет первое наступление, решили усовершенствовать оборонную систему города. А именно, они решили установить противопехотные ежи.

Для того чтобы добиться максимального эффекта от баррикады, жители Волантиса решили составить план конструкции. Система ежей представлена на плане в виде непересекающихся отрезков на прямой.

Благодаря шпионам, этот план попал в руки пентосского военачальника. Узнав о том, что жители Волантиса не собираются сдаваться без боя, военачальник огорчился. К тому же он уже составил собственный план наступления: сформировал шеренги солдат, отметив их на своем плане системой непересекающихся отрезков на прямой, подобно тому, как это сделали люди из Волантиса. Но, взяв себя в руки, военачальник решил сдвинуть своих солдат так, чтобы после нанесения отрезков, соответствующих солдатам, на прямую с отрезками, соответствующими противопехотным ежам, суммарная длина пересечения отрезков была минимальна.

Однако, если военачальник сдвигает какой-либо из отрезков, все остальные отрезки сдвигаются на столько же в том же направлении. Помимо того, левые и правые границы всех отрезков должны быть не меньше заданного $l$ и не больше $r$. Также сдвигать отрезки можно только на целое число.

Помогите пентосскому военачальнику, найдите длину минимального суммарного пересечения отрезков.

В первой строке входного файла дано два числа $n$ и $m$ --- число отрезков с противопехотными ежами и число отрезков с солдатами соответственно ($1 \le n, m \le 300$).

В следующей строке даны два числа $l$ и $r$ --- границы, описанные в условии ($-10^9 \le l, r \le 10^9$).

Далее следуют $n$ строк с описанием системы противопехотных ежей в Волантисе. Противопехотный ёж описывается двумя числами $a\_i, b\_i$ --- отрезком на прямой с началом в точке $a\_i$ и концом в точке $b\_i$ ($l \le a\_i \le b\_i \le r$).

Далее следуют $m$ строк с аналогичным описанием шеренг солдат Пентоса.

Все отрезки даны в порядке возрастания координат их левых концов. Для всех отрезков, описывающих шеренги солдат, координата начала $i+1$-го отрезка всегда больше координаты конца $i$-го отрезка. Аналогичное утверждение верно и про отрезки, описывающие систему противопехотных ежей.

В единственной строке выходного файла выведите значение длины минимального суммарного пересечения отрезков при каком-то сдвиге отрезков, описывающих шеренги солдат. Сам сдвиг выводить не надо.

Пусть отрезки первого типа --- система противопехотных ежей, второго типа - шеренги солдат.

Тогда в первом примере можно сдвинуть отрезки второго типа на 1 вправо. Тогда отрезки первого и второго типа не будут пересекаться, следовательно ответ будет равен 0.

Во втором примере выгодно сдвинуть отрезки второго типа на 1 влево.

Отрезки первого типа двигать нельзя.