| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 5 | 5 | 1 | 100.000% |
Неожиданно для всех между Волантисом и Пентосом разразилась война. Жители Волантиса, зная, что вот-вот будет первое наступление, решили усовершенствовать оборонную систему города. А именно, они решили установить противопехотные ежи.
Для того чтобы добиться максимального эффекта от баррикады, жители Волантиса решили составить план конструкции. Система ежей представлена на плане в виде непересекающихся отрезков на прямой.
Благодаря шпионам, этот план попал в руки пентосского военачальника. Узнав о том, что жители Волантиса не собираются сдаваться без боя, военачальник огорчился. К тому же он уже составил собственный план наступления: сформировал шеренги солдат, отметив их на своем плане системой непересекающихся отрезков на прямой, подобно тому, как это сделали люди из Волантиса. Но, взяв себя в руки, военачальник решил сдвинуть своих солдат так, чтобы после нанесения отрезков, соответствующих солдатам, на прямую с отрезками, соответствующими противопехотным ежам, суммарная длина пересечения отрезков была минимальна.
Однако, если военачальник сдвигает какой-либо из отрезков, все остальные отрезки сдвигаются на столько же в том же направлении. Помимо того, левые и правые границы всех отрезков должны быть не меньше заданного $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$-го отрезка. Аналогичное утверждение верно и про отрезки, описывающие систему противопехотных ежей.
В единственной строке выходного файла выведите значение длины минимального суммарного пересечения отрезков при каком-то сдвиге отрезков, описывающих шеренги солдат. Сам сдвиг выводить не надо.
3 2 0 5 0 1 2 3 4 5 0 1 2 3
0
2 3 0 7 1 3 6 7 1 2 3 5 6 7
1
Пусть отрезки первого типа --- система противопехотных ежей, второго типа - шеренги солдат.
Тогда в первом примере можно сдвинуть отрезки второго типа на 1 вправо. Тогда отрезки первого и второго типа не будут пересекаться, следовательно ответ будет равен 0.
Во втором примере выгодно сдвинуть отрезки второго типа на 1 влево.
Отрезки первого типа двигать нельзя.