Вы счастливый мэр процветающей столицы Берляндии, но вот незадача~--- в пригороде поселился ужасный монстр, который атакует торговые караваны, курсирующие между столицей и соседними городами. Чтобы избавиться от монстра, вы решили нанять команду героев в городской гильдии авантюристов. 

Гильдия предлагает $n$ воинов и у $i$-го воина $h_i$ единиц здоровья и $d_i$ единиц атаки. У монстра, которого надо убить, $a$ единиц здоровья.

Пока у монстра осталось положительное число единиц здоровья и остался хотя бы один герой с положительным количеством единиц здоровья, происходит следующее:
\begin{enumerate}
\item Сначала каждый живой герой наносит монстру урон, равный значению его атаки. Если здоровье монстра упало до нуля, битва завершается;
\item Затем, если монстр еще жив, он наносит каждому герою по единице урона. Каждый герой, чей уровень здоровья упал до нуля, умирает.
\end{enumerate}

Так как казна ограничена, вы хотите нанять наименьшее число героев, чтобы убить монстра. Но вы также не хотите, чтобы умер \textbf{хотя бы один} из героев команды, поэтому вам надо нанять наименьшее число героев, чтобы они могли убить монстра без потерь.
