У маленького Саши есть две подруги, которых он хочет порадовать подарками на Восьмое марта. Для этого он отправился в самый большой торговый центр в городе.
В торговом центре есть \(n\) отделов, в каждом из которых находятся ровно два магазина. Для удобства пронумеруем отделы целыми числами от \(1\) до \(n\). Известно, что подарки в первом магазине \(i\)-го отдела стоят \(a_i\) рублей, а во втором магазине \(i\)-го отдела — \(b_i\) рублей.
Войдя в торговый центр, Саша посетит каждый из \(n\) отделов торгового центра, причем в каждом отделе он зайдет ровно в один магазин. Когда Саша попадет в \(i\)-й отдел, он выполнит ровно одно из двух действий:
- Купить подарок первой подруге, потратив на это \(a_i\) рублей.
- Купить подарок второй подруге, потратив на это \(b_i\) рублей.
Для каждой подруги Саша собирается купить хотя бы один подарок. Более того, он хочет подобрать подарки таким образом, чтобы разность цен самых дорогих подарков, купленных подругам, была как можно меньше, чтобы никто не обиделся.
Более формально: пусть \(m_1\) — максимальная цена подарка, купленного первой подруге, а \(m_2\) — максимальная цена подарка, купленного второй подруге. Саша хочет выбрать подарки таким образом, чтобы минимизировать величину \(\lvert m_1 - m_2 \rvert\).
Выходные данные
Выведите одно целое число — минимальную разность цен самых дорогих подарков, купленных подругам.
Примечание
В первом наборе входных данных у Саши есть два возможных варианта действий: купить подарок первой подруге в первом отделе, а второй подруге — во втором отделе, или наоборот. В первом случае \(m_1 = m_2 = 1\), а во втором случае — \(m_1 = m_2 = 2\). В обоих случаях ответ равен \(0\). Во втором наборе входных данных можно купить подарки для первой подруги в \(2\)-м, \(4\)-м и \(5\)-м отделах, а для второй подруги — в \(1\)-м и \(3\)-м отделах. Таким образом, \(m_1 = \max(2, 4, 2) = 4\), \(m_2 = \max(5, 3) = 5\). Ответ равен \(\lvert 4 - 5 \rvert = 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2
1 2
2 1
5
1 5
2 7
3 3
4 10
2 5
|
0
1
|