Занимательный эксперимент

Маленький Дима увлекается физикой и обожает эксперименты. Сегодня он решил поставить очередной познавательный опыт.

У Димы есть бесконечно высокая труба, на дне которой находится клапан, позволяющий при активации уменьшить уровень воды в трубе ровно на один сантиметр. Внутри трубы расположены $n$ датчиков. Датчик с номером $i$ находится на высоте $h_i$ сантиметров от дна трубы, при этом датчик с б\'{о}льшим номером находится на большей высоте. Все датчики подключены к цепи управления клапаном, которая опрашивает датчики по очереди, начиная c датчика с номером $n$ и заканчивая датчиком с номером $1$, при этом датчик с номером $i$ опрашивается $v_i$ раз подряд. Во время опроса датчика с номером $i$, если уровень воды не ниже высоты, на которой находится датчик, открывается клапан, и уровень воды понижается на один сантиметр.

Дима решил проводить эксперимент следующим образом.

1. Дима выбирает некоторое целое число $x$.
2. В начале каждой секунды Дима заливает в трубу воду так, чтобы уровень воды в трубе повысился на $x$ сантиметров.
3. Затем в эту же секунду Дима запускает цепь управления, в результате чего уровень воды понижается.
4. Если в конце секунды уровень воды не меньше, чем $H$ сантиметров, то Дима заканчивает эксперимент. В противном случае Дима продолжает эксперимент, заливая в трубу ещё воды в начале следующей секунды.

Считайте, что процесс добавления воды и работы цепи управления занимает пренебрежимо малое время. Также считайте, что труба достаточно высокая, чтобы вместить любое количество воды. В начале эксперимента воды в трубе нет.

Через $T$ секунд Димина мама вернётся домой и будет очень недовольна, если увидит, как Дима занимается переливанием воды вместо решения задач заочного тура Открытой олимпиады по программированию. Поэтому Дима решил выбрать $x$ так, чтобы эксперимент закончился не позже, чем через $T$ секунд. Кроме того, Дима не хочет носить много воды и хочет выбрать минимальное подходящее $x$. Помогите Диме успеть провести эксперимент до возвращения мамы домой.

В первой строке входных данных заданы три целых числа $n$, $H$ и $T$ ($1 \leq n \leq 100\,000$, $1 \leq H, T \leq 10^9$) --- количество датчиков, требуемый уровень воды и время до прихода мамы соответственно.

Следующие $n$ строк описывают имеющиеся в трубе датчики. В $i$-й из этих строк находятся два целых числа $h_i$ и $v_i$ ($1 \leq h_i \leq H, 1 \leq v_i \leq 10^9$) --- высота, на которой находится датчик с номером $i$ и количество раз, которое цепь управления опрашивает этот датчик.

Гарантируется, что $1 \le h_1 < h_2 < \ldots < h_n \le H$.

Выведите одно целое число --- минимальное значение величины $x$, которое позволит Диме завершить эксперимент за не более чем $T$ секунд.

В первом тестовом примере эксперимент происходит следующим образом.

1. В начале первой секунды Дима зальёт воду и уровень станет равен $5$ сантиметрам. Так как вода находится ниже единственного датчика, во время работы цепи он ни разу не сработает и уровень воды не изменится.
2. В начале второй секунды уровень воды станет равен $10$ сантиметрам. После этого датчик будет опрошен $4$ раза. Перед первым, вторым и третьим опрашиванием уровень воды в трубе будет составлять $10$, $9$ и $8$ сантиметров соответственно, поэтому вода будет сливаться каждый раз. Перед четвёртым опрашиванием уровень воды будет находиться на отметке в $7$ сантиметров и клапан активирован не будет, а значит, уровень воды не изменится.
3. В начале третьей секунды Дима поднимет уровень воды до $12$ сантиметров, после чего датчик сработает четыре раза подряд и уровень воды упадёт до $8$ сантиметров.
4. В начале четвёртой секунды Дима поднимает уровень воды до $13$ сантиметров, датчик сработает четыре раза и уровень воды опустится до $9$ сантиметров.
5. В начале пятой секунды Дима поднимет уровень воды до $14$ сантиметров, датчик сработает четыре раза, уровень воды понизится до $10$ сантиметров. Таким образом Дима закончит эксперимент за $5$ секунд, как раз в момент когда мама будет на пороге квартиры.

Можно проверить, что ни при каком меньшем значении $x$ Дима не успеет закончить опыт до прихода мамы.

Рассмотрим ход эксперимента в четвёртом тестовом примере.

1. В начале первой секунды Дима зальёт воду в трубу, и уровень воды установится на отметке в $12$ сантиметров. Датчик на высоте $15$ не сработает, датчик на высоте $6$ сработает один раз, в результате чего уровень воды понизится до $11$ сантиметров. После этого датчик на высоте $1$ сработает $5$ раз и уровень воды станет равным $6$.
2. В начале второй секунды Дима поднимет уровень воды до $18$ сантиметров. После этого датчики на высотах $15$ и $6$ сработают по разу, а датчик на высоте $1$ --- $5$ раз, в результате чего клапан будет активирован $7$ раз, и уровень воды снизится до $11$ сантиметров.
3. В начале третьей секунды Дима зальёт воду до отметки в $23$ сантиметра. Как и в прошлую секунду, датчики сработают $7$ раз, понижая уровень воды до $16$ сантиметров, после чего Дима завершит свой эксперимент.