D. Запись на экзамен
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обычно Новый год у всех ассоциируется с ёлкой и праздничным столом, однако у студентов Новый год ассоциируется с сессией. Наступило 31 декабря, и студенты второго курса записались на сдачу экзамена.

Всего существует $$$n$$$ дней, в которые можно сдавать экзамен. Каждый студент записался для сдачи на один из этих дней. Получилось, что в $$$i$$$-й день экзамен желают сдать $$$a_{i}$$$ студентов, а максимальное количество студентов, у которых преподаватели готовы принять экзамен в этот день, равно $$$b_{i}$$$.

Преподавателям необходимо обеспечить всем студентам возможность сдавать экзамен, поэтому некоторых студентов может быть придется переместить на другой день. Преподаватели могут выбрать любое множество студентов и назначить каждому из них любой день для сдачи.

Если студент желал сдать экзамен в $$$i$$$-й день, а преподаватели в итоге перенесли его на $$$j$$$-й день, то недовольство этого студента будет равно $$$|i - j|$$$.

Помогите преподавателям распределить студентов так, чтобы для всех $$$i$$$ в $$$i$$$-й день экзамен сдавали не более $$$b_i$$$ студентов, а максимальное недовольство среди студентов было минимальным.

Входные данные

В первой строке ввода дано одно целое число $$$n$$$ — количество дней, в которые можно сдавать экзамен ($$$1 \le n \le 10^{6}$$$).

Во второй строке ввода даны $$$n$$$ целых чисел $$$a_{i}$$$ — количество студентов, которые желают сдать экзамен в $$$i$$$-й день ($$$1 \le a_i \le 10^{9}$$$).

В третьей строке ввода даны $$$n$$$ целых чисел $$$b_{i}$$$ — максимальное количество студентов, у которых преподаватели готовы принять экзамен в $$$i$$$-й день ($$$0 \le b_i \le 10^{9}$$$).

Выходные данные

Выведите единственное целое число — для какого минимального $$$k$$$ можно добиться, чтобы недовольство любого студента не превышало $$$k$$$. Если решения не существует, следует вывести $$$-1$$$.

Примеры
Входные данные
4
6 14 70 1
70 3 16 5
Выходные данные
2
Входные данные
1
2
2
Выходные данные
0
Входные данные
1
3
2
Выходные данные
-1
Примечание

Рассмотрим первый пример. Заметим, что 70 студентов хотят сдавать экзамен в третий день, но суммарно во второй, третий и четвертый день сдать экзамен смогут только 24 студента, поэтому ответ не меньше 2.

Следующий алгоритм перераспределяет студентов по дням, переместив каждого студента не более чем на 2 дня.

  • $$$6, 14, 70, 1$$$ — исходная запись студентов;
  • $$$6, 70, 14, 1$$$ — перенесли всех студентов с третьего дня на второй, а всех студентов со второго дня на третий;
  • $$$70, 6, 14, 1$$$ — перенесли всех студентов со второго дня на первый, а всех студентов с первого дня на второй;
  • $$$70, 6, 11, 4$$$ — перенесли трех студентов с третьего дня на четвертый;
  • $$$70, 3, 14, 4$$$ — перенесли трех студентов со второго дня на третий;

Заметим, что каждый студент был перемещен не более чем на два дня от своей исходной записи.