Есть \(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\)).
Какое минимальное количество ходов нужно сделать, чтобы грабители оказались в безопасной конфигурации?
Выходные данные
Выведите единственное целое число: минимальное количество ходов, необходимое, чтобы грабители оказались в безопасной конфигурации.
Примечание
В первом тесте вы можете подвинуть всех грабителей направо три раза. После этого будет один грабитель в координатах \((3, 0)\).
Конфигурация грабителей будет безопасной, потому что единственный прожектор не освещает грабителя, так как он в координатах \((2, 3)\), а \(3 > 2\).
Во втором тесте вы можете подвинуть всех грабителей направо два раза и вверх два раза. После этого грабители будут в координатах \((3, 8)\), \((8, 3)\).
Легко увидеть, что такая конфигурация безопасна.
Можно доказать, что невозможно получить безопасную конфигурацию, используя не больше, чем \(3\) хода.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
0 0
2 3
|
3
|
|
2
|
2 3
1 6
6 1
10 1
1 10
7 7
|
4
|
|
3
|
1 2
0 0
0 0
0 0
|
1
|
|
4
|
7 3
0 8
3 8
2 7
0 10
5 5
7 0
3 5
6 6
3 11
11 5
|
6
|