В Берляндском ГУ сегодня проходит очередной контест для студентов. \(n\) студентов пришли, каждый принес с собой ноутбук. Однако, как оказалось, все забыли свои зарядные устройства!
Пусть студенты пронумерованы от \(1\) до \(n\). Ноутбук \(i\)-го студента заряжен на \(a_i\) в начале контеста, и он использует \(b_i\) заряда в минуту (то есть, если заряд ноутбука \(c\) в начале некоторой минуты, то он становится \(c - b_i\) к началу следующей минуты). Контест длится \(k\) минут.
Поликарп (тренер Берляндского ГУ) решил купить ровно одно зарядное устройство так, чтобы все студенты смогли успешно завершить контест. Он покупает зарядное устройство в момент начала контеста.
Поликарп может купить зарядное устройство любой неотрицательной (нулевой или больше) целой мощности. Мощность выбирается до покупки, она не может быть изменена позднее. Пусть выбранная мощность \(x\). В начале каждой минуты (от минуты начала контеста до последней минуты контеста) он может подключить зарядное устройство в ноутбук любого из студентов и заряжать его целое число минут. Если ноутбук потребляет \(b_i\) заряда в минуту, то потребление становится \(b_i - x\) в минуту, когда подключено зарядное устройство. Отрицательное потребление значит, что заряд ноутбука увеличивается. Заряд любого ноутбука не ограничен, он может быть бесконечно большим. Зарядное устройство может быть включено не более чем в один ноутбук в одно и то же время.
Студент успешно завершает контест, если заряд его ноутбука равен или больше нуля в начале каждой минуты контеста (от минуты начала контеста до последней минуты контеста). Заряд ноутбука в минуту, когда когда контест завершается, не важен.
Помогите Поликарпу определить минимальную возможную мощность зарядного устройства такую, чтобы все студенты смогли успешно завершить контест. Также сообщите, если такого зарядного устройства не существует.
Выходные данные
Выведите единственное неотрицательное целое число — минимальная возможная мощность зарядного устройства такая, чтобы все студенты смогли успешно завершить контест.
Если такого зарядного устройства не существует, то выведите -1.
Примечание
Взглянем на состояние ноутбуков в начале каждый минуты в первом примере с зарядным устройством мощности \(5\):
- заряд: \([3, 2]\), подключим зарядное устройство в ноутбук 1;
- заряд: \([3 - 4 + 5, 2 - 2] = [4, 0]\), подключим зарядное устройство в ноутбук 2;
- заряд: \([4 - 4, 0 - 2 + 5] = [0, 3]\), подключим зарядное устройство в ноутбук 1;
- заряд: \([0 - 4 + 5, 3 - 2] = [1, 1]\).
Контест завершается после четвертой минуты.
Однако, рассмотрим зарядное устройство мощности \(4\):
- заряд: \([3, 2]\), подключим зарядное устройство в ноутбук 1;
- заряд: \([3 - 4 + 4, 2 - 2] = [3, 0]\), подключим зарядное устройство в ноутбук 2;
- заряд: \([3 - 4, 0 - 2 + 4] = [-1, 2]\), у первого ноутбука становится отрицательный заряд, поэтому первый студент не может успешно завершить контест.
В четвертом примере сколь бы мощным не было зарядное устройство, один из студентов никогда не сможет успешно завершить контест.