- Финальный
- Отборочный
- 3-й квал
- 2-й квал
- 1-й квал
- Разогревочный
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 |
|
|