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

문제

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

У Димы есть бесконечно высокая труба, на дне которой находится клапан, позволяющий при активации уменьшить уровень воды в трубе ровно на один сантиметр. Внутри трубы расположены $nn$ датчиков. Датчик с номером $ii$ находится на высоте $h_{i}h\_i$ сантиметров от дна трубы, при этом датчик с б\'{о}льшим номером находится на большей высоте. Все датчики подключены к цепи управления клапаном, которая опрашивает датчики по очереди, начиная c датчика с номером $nn$ и заканчивая датчиком с номером $11$, при этом датчик с номером $ii$ опрашивается $v_{i}v\_i$ раз подряд. Во время опроса датчика с номером $ii$, если уровень воды не ниже высоты, на которой находится датчик, открывается клапан, и уровень воды понижается на один сантиметр.

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

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

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

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

입력

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

Следующие $nn$ строк описывают имеющиеся в трубе датчики. В $ii$-й из этих строк находятся два целых числа $h_{i}h\_i$ и $v_{i}v\_i$ ($1\le h_i\le H,1\le v_i\le {10}^{9}1\; \backslash leq\; h\_i\; \backslash leq\; H,\; 1\; \backslash leq\; v\_i\; \backslash leq\; 10^9$) --- высота, на которой находится датчик с номером $ii$ и количество раз, которое цепь управления опрашивает этот датчик.

Гарантируется, что .

출력

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

힌트

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

1. В начале первой секунды Дима зальёт воду и уровень станет равен $55$ сантиметрам. Так как вода находится ниже единственного датчика, во время работы цепи он ни разу не сработает и уровень воды не изменится.
2. В начале второй секунды уровень воды станет равен $1010$ сантиметрам. После этого датчик будет опрошен $44$ раза. Перед первым, вторым и третьим опрашиванием уровень воды в трубе будет составлять $1010$, $99$ и $88$ сантиметров соответственно, поэтому вода будет сливаться каждый раз. Перед четвёртым опрашиванием уровень воды будет находиться на отметке в $77$ сантиметров и клапан активирован не будет, а значит, уровень воды не изменится.
3. В начале третьей секунды Дима поднимет уровень воды до $1212$ сантиметров, после чего датчик сработает четыре раза подряд и уровень воды упадёт до $88$ сантиметров.
4. В начале четвёртой секунды Дима поднимает уровень воды до $1313$ сантиметров, датчик сработает четыре раза и уровень воды опустится до $99$ сантиметров.
5. В начале пятой секунды Дима поднимет уровень воды до $1414$ сантиметров, датчик сработает четыре раза, уровень воды понизится до $1010$ сантиметров. Таким образом Дима закончит эксперимент за $55$ секунд, как раз в момент когда мама будет на пороге квартиры.

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

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

1. В начале первой секунды Дима зальёт воду в трубу, и уровень воды установится на отметке в $1212$ сантиметров. Датчик на высоте $1515$ не сработает, датчик на высоте $66$ сработает один раз, в результате чего уровень воды понизится до $1111$ сантиметров. После этого датчик на высоте $11$ сработает $55$ раз и уровень воды станет равным $66$.
2. В начале второй секунды Дима поднимет уровень воды до $1818$ сантиметров. После этого датчики на высотах $1515$ и $66$ сработают по разу, а датчик на высоте $11$ --- $55$ раз, в результате чего клапан будет активирован $77$ раз, и уровень воды снизится до $1111$ сантиметров.
3. В начале третьей секунды Дима зальёт воду до отметки в $2323$ сантиметра. Как и в прошлую секунду, датчики сработают $77$ раз, понижая уровень воды до $1616$ сантиметров, после чего Дима завершит свой эксперимент.