Буровая установка «Мегабур 2022» для прокладки туннелей метро Байтсбурга имеет $$$n$$$ двигателей. Питание установки устроено таким образом, что на все двигатели подается одно и то же целочисленное напряжение $$$x$$$.

У каждого двигателя есть два режима, если на него подается напряжение $$$x$$$, то $$$i$$$-й двигатель работает в первом режиме, если $$$x \le z_i$$$ и во втором режиме, если $$$x \gt z_i$$$.

При этом $$$i$$$-й двигатель характеризуется удельной мощностью $$$a_i$$$ в первом режиме и $$$b_i$$$ во втором режиме. Это означает, что увеличение напряжения на 1 когда двигатель находится в первом режиме, приводит к увеличению его мощности на $$$a_i$$$, а во втором режиме приводит к увеличению его мощности на $$$b_i$$$. Иначе говоря, при подаче напряжения $$$x$$$, если $$$i$$$-й двигатель находится в первом режиме он работает с мощностью $$$a_i x$$$, а если во втором режиме, то с мощностью $$$a_iz_i + b_i(x-z_i)$$$.

Для прокладки туннеля суммарная мощность двигателей должна быть не меньше $$$p$$$. Какое минимальное целочисленное напряжение необходимо подать на установку, чтобы суммарная мощность двигателей была больше или равна $$$p$$$?

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