3-й квалификационный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"B" Смертный бой
Ограничение по времени 1 секунда
Ограничение по памяти 256 мегабайт

Недавно Вася начал играть в новую компьютерную игру. В конце первого уровня его ждал босс, которого нужно победить, чтобы продолжить проходить игру. У Васи есть отряд из n персонажей, i-й из которых имеет hi единиц здоровья и ai единиц атаки. Босс же имеет H единиц здоровья и A единиц атаки.

Сражение происходит следующим образом:

  • Если у Васи больше нет персонажей, он проиграл;
  • Иначе, он выбирает одного из них и выставляет на бой против босса;
  • Пусть Вася выбрал персонажа номер i. Тогда:
    • Персонаж нападает на босса и снимает ему ai единиц здоровья;
    • Если босс еще жив, то есть его количество единиц здоровья положительно, он нападает в ответ и снимает персонажу A единиц здоровья;
    • Пока и персонаж и босс оба живы, действия повторяются.
  • Если босс умер, сражение заканчивается, Вася побеждает. В противном случае все действия повторяются.

Так как Васе еще предстоит проходить следующие уровни, он хочет потерять как можно меньше персонажей. Помогите ему — найдите минимальное возможное количество персонажей, которое он может потерять в сражении с боссом. Если же Васе не победить даже используя всех персонажей, выведите  - 1.

Рассмотрим тестовые примеры.

В первом примере Вася может сначала отправить сражаться персонажа 2, который три раза нанесет удар, уменьшит количество единиц здоровья у босса на 12, и лишь затем погибнет, а затем отправить персонажа 3, который сразу же снимет у босса уже 6 единиц здоровья и убьет его. Таким образом, Вася потеряет только одного персонажа.

Во втором примере даже если Вася отправит в бой по очереди всех персонажей, босс не будет убит.

Формат входных данных

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 1000).

Каждый из следующих t тестов описывается следующим образом: в первой строке описания теста содержится три целых числа n, H, A — количество персонажей у Васи, количество единиц здоровья и атаки у босса соответственно (1 ≤ n ≤ 105, 1 ≤ H, A ≤ 109).

В каждой из следующих n строк содержится два целых числа hi, ai — количество единиц здоровья и атаки у i-го персонажа соответственно (1 ≤ hi, ai ≤ 109).

Гарантируется, что сумма n во всех тестах одних входных данных не превосходит 105.

Формат выходных данных

Для каждого теста выведите ответ на него — минимальное количество персонажей, которое может потерять Вася, чтобы одержать победу над боссом, или  - 1, если он в любом случае проиграет сражение.

Примеры
Входные данные
2
4 18 4
4 5
9 4
1 6
3 3
4 27 4
4 5
9 4
1 6
3 3
Выходные данные
1
-1
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.