21. Интервалы

На числовом отрезке $[l, r]$ выделены интервалы синего и красного цветов, с концами в целых числах. Разрешено выбрать целое число $k$ и сдвинуть все отрезки красного цвета на $k$ единиц вправо или влево, если ни один из отрезков не выйдет за границы $[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$ строк с парой чисел $c_i, d_i$ — описанием красного отрезка на прямой с началом в точке $c_i$ и концом в точке $d_i$ ($l \le c_i \le d_i \le r$).

Гарантируется, что синие отрезки не пересекаются между собой и красные отрезки также не пересекаются между собой.

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

В первом тесте даны два отрезка: синий отрезок $[0, 4]$ и красный отрезок $[1, 3]$. При сдвиге на $2$ единицы вправо красный отрезок становится отрезком $[3, 5]$ и длина пересечения равна $1$. Сильнее сдвинуть отрезок вправо нельзя, так как красный отрезок тогда выйдет за допустимый интервал.

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