Grakn Forces 2020 |
---|
Закончено |
Есть $$$n$$$ грабителей в координатах $$$(a_1, b_1)$$$, $$$(a_2, b_2)$$$, ..., $$$(a_n, b_n)$$$ и $$$m$$$ прожекторов в координатах $$$(c_1, d_1)$$$, $$$(c_2, d_2)$$$, ..., $$$(c_m, d_m)$$$.
За один ход вы можете подвинуть всех грабителей направо (увеличить $$$a_i$$$ всех грабителей на единицу) или подвинуть всех грабителей вверх (увеличить $$$b_i$$$ всех грабителей на единицу). Обратите внимание, что вы должны либо увеличить все $$$a_i$$$, либо все $$$b_i$$$, вы не можете увеличить $$$a_i$$$ некоторых грабителей и $$$b_i$$$ некоторых других грабителей за одну операцию.
Прожектор $$$j$$$ освещает грабителя $$$i$$$, если $$$a_i \leq c_j$$$ и $$$b_i \leq d_j$$$.
Конфигурация грабителей называется безопасной, если ни один прожектор не освещает ни одного грабителя (то есть нет такой пары $$$i,j$$$, что прожектор $$$j$$$ освещает грабителя $$$i$$$).
Какое минимальное количество ходов нужно сделать, чтобы грабители оказались в безопасной конфигурации?
В первой строке находится два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 2000$$$): количество грабителей и количество прожекторов.
Каждая из следующих $$$n$$$ строк содержит два целых числа $$$a_i$$$, $$$b_i$$$ ($$$0 \leq a_i, b_i \leq 10^6$$$), координаты грабителей.
Каждая из следующих $$$m$$$ строк содержит два целых числа $$$c_i$$$, $$$d_i$$$ ($$$0 \leq c_i, d_i \leq 10^6$$$), координаты прожекторов.
Выведите единственное целое число: минимальное количество ходов, необходимое, чтобы грабители оказались в безопасной конфигурации.
1 1 0 0 2 3
3
2 3 1 6 6 1 10 1 1 10 7 7
4
1 2 0 0 0 0 0 0
1
7 3 0 8 3 8 2 7 0 10 5 5 7 0 3 5 6 6 3 11 11 5
6
В первом тесте вы можете подвинуть всех грабителей направо три раза. После этого будет один грабитель в координатах $$$(3, 0)$$$.
Конфигурация грабителей будет безопасной, потому что единственный прожектор не освещает грабителя, так как он в координатах $$$(2, 3)$$$, а $$$3 > 2$$$.
Во втором тесте вы можете подвинуть всех грабителей направо два раза и вверх два раза. После этого грабители будут в координатах $$$(3, 8)$$$, $$$(8, 3)$$$.
Легко увидеть, что такая конфигурация безопасна.
Можно доказать, что невозможно получить безопасную конфигурацию, используя не больше, чем $$$3$$$ хода.
Название |
---|