30732번 - Занимательный эксперимент 다국어

문제

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

У Димы есть бесконечно высокая труба, на дне которой находится клапан, позволяющий при активации уменьшить уровень воды в трубе ровно на один сантиметр. Внутри трубы расположены $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ドル$ сантиметров, после чего Дима завершит свой эксперимент.