D. Напряженная тренировка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндском ГУ сегодня проходит очередной контест для студентов. $$$n$$$ студентов пришли, каждый принес с собой ноутбук. Однако, как оказалось, все забыли свои зарядные устройства!

Пусть студенты пронумерованы от $$$1$$$ до $$$n$$$. Ноутбук $$$i$$$-го студента заряжен на $$$a_i$$$ в начале контеста, и он использует $$$b_i$$$ заряда в минуту (то есть, если заряд ноутбука $$$c$$$ в начале некоторой минуты, то он становится $$$c - b_i$$$ к началу следующей минуты). Контест длится $$$k$$$ минут.

Поликарп (тренер Берляндского ГУ) решил купить ровно одно зарядное устройство так, чтобы все студенты смогли успешно завершить контест. Он покупает зарядное устройство в момент начала контеста.

Поликарп может купить зарядное устройство любой неотрицательной (нулевой или больше) целой мощности. Мощность выбирается до покупки, она не может быть изменена позднее. Пусть выбранная мощность $$$x$$$. В начале каждой минуты (от минуты начала контеста до последней минуты контеста) он может подключить зарядное устройство в ноутбук любого из студентов и заряжать его целое число минут. Если ноутбук потребляет $$$b_i$$$ заряда в минуту, то потребление становится $$$b_i - x$$$ в минуту, когда подключено зарядное устройство. Отрицательное потребление значит, что заряд ноутбука увеличивается. Заряд любого ноутбука не ограничен, он может быть бесконечно большим. Зарядное устройство может быть включено не более чем в один ноутбук в одно и то же время.

Студент успешно завершает контест, если заряд его ноутбука равен или больше нуля в начале каждой минуты контеста (от минуты начала контеста до последней минуты контеста). Заряд ноутбука в минуту, когда когда контест завершается, не важен.

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

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

В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 2 \cdot 10^5$$$) — количество студентов (и ноутбуков, соответственно) и продолжительность контеста в минутах.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — начальный заряд ноутбука каждого из студентов.

В третьей строке записаны $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^7$$$) — потребление ноутбука каждого из студентов.

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

Выведите единственное неотрицательное целое число — минимальная возможная мощность зарядного устройства такая, чтобы все студенты смогли успешно завершить контест.

Если такого зарядного устройства не существует, то выведите -1.

Примеры
Входные данные
2 4
3 2
4 2
Выходные данные
5
Входные данные
1 5
4
2
Выходные данные
1
Входные данные
1 6
4
2
Выходные данные
2
Входные данные
2 2
2 10
3 15
Выходные данные
-1
Примечание

Взглянем на состояние ноутбуков в начале каждый минуты в первом примере с зарядным устройством мощности $$$5$$$:

  1. заряд: $$$[3, 2]$$$, подключим зарядное устройство в ноутбук 1;
  2. заряд: $$$[3 - 4 + 5, 2 - 2] = [4, 0]$$$, подключим зарядное устройство в ноутбук 2;
  3. заряд: $$$[4 - 4, 0 - 2 + 5] = [0, 3]$$$, подключим зарядное устройство в ноутбук 1;
  4. заряд: $$$[0 - 4 + 5, 3 - 2] = [1, 1]$$$.

Контест завершается после четвертой минуты.

Однако, рассмотрим зарядное устройство мощности $$$4$$$:

  1. заряд: $$$[3, 2]$$$, подключим зарядное устройство в ноутбук 1;
  2. заряд: $$$[3 - 4 + 4, 2 - 2] = [3, 0]$$$, подключим зарядное устройство в ноутбук 2;
  3. заряд: $$$[3 - 4, 0 - 2 + 4] = [-1, 2]$$$, у первого ноутбука становится отрицательный заряд, поэтому первый студент не может успешно завершить контест.

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