F. Напиши контест
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп, друг Аркадия, готовится к олимпиаде по программированию и решил написать контест. Контест состоит из $$$n$$$ задач и длится $$$T$$$ минут. Каждая из задач задаётся двумя целыми положительными числами $$$a_i$$$ и $$$p_i$$$ — её сложность и количество баллов за её решение

Опыт Поликарпа подсказывает, что его навык характеризуется положительным вещественным числом $$$s$$$, причем изначально $$$s=1.0$$$. Для решения $$$i$$$-й задачи Поликарпу требуется $$$a_i/s$$$ минут.

Поликарп очень любит смотреть сериалы, поэтому перед решением каждой из задач он обязательно будет смотреть одну серию. За время просмотра серии его навык уменьшается на $$$10\%$$$, то есть навык $$$s$$$ уменьшается до $$$0.9s$$$. Каждая серия имеет продолжительность $$$10$$$ минут. Приняв решение работать над задачей, Поликарп обязательно сначала смотрит серию, а затем решает без перерывов задачу в течение $$$a_i/s$$$ минут, где $$$s$$$ — его текущий навык. При вычислении $$$a_i/s$$$ округление не используется, просто производится деление целого числа $$$a_i$$$ на вещественное число $$$s$$$.

Также Поликарп может тренироваться. Тренируясь в течение $$$t$$$ минут, он увеличивает свой навык на величину $$$C \cdot t$$$, где $$$C$$$ — заданная положительная вещественная константа. Тренироваться Поликарп может только до решения всех задач (и до просмотра сериалов). Продолжительность тренировки может быть любым вещественным числом.

Поликарпу стало интересно, какое наибольшее количество баллов он сможет заработать за все время контеста. Задачи можно решать в любом порядке, тренироваться же можно только до решения первой задачи.

Входные данные

В первой строке записано целое число $$$tc$$$ ($$$1 \le tc \le 20$$$) — количество тестовых случаев. Далее следуют $$$tc$$$ тестовых случаев.

В первой строке каждого тестового случая записано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество задач в контесте.

Вторая строка теста содержит два вещественных числа $$$C, T$$$ ($$$0 < C < 10$$$, $$$0 \le T \le 2 \cdot 10^5$$$), где $$$C$$$ — параметр, характеризующий эффективность тренировок, а $$$T$$$ — длительность контеста в минутах. Значения $$$C, T$$$ записаны ровно с тремя знаками после десятичной точки.

Каждая из следующих $$$n$$$ строк теста содержит характеристики соответствующей задачи — два целых числа $$$a_i, p_i$$$ ($$$1 \le a_i \le 10^4$$$, $$$1 \le p_i \le 10$$$) — сложность и количество баллов за её решение.

Гарантируется, что значение $$$T$$$ в каждом тесте таково, что изменение этого числа на $$$0.001$$$ в любую сторону не изменит ответ на тест.

Обратите внимание, что во взломах вы можете использовать только $$$tc = 1$$$.

Выходные данные

Выведите $$$tc$$$ целых чисел — максимальное возможное количество баллов в каждом тестовом случае.

Примеры
Входные данные
2
4
1.000 31.000
12 3
20 6
30 1
5 1
3
1.000 30.000
1 10
10 10
20 8
Выходные данные
7
20
Примечание

В первом примере набрать $$$7$$$ баллов Поликарп может следующим образом:

  1. Сначала он тренируется $$$4$$$ минуты, увеличивая $$$s$$$ до величины $$$5$$$;
  2. Потом хочет решить $$$4$$$-ю задачу: смотрит сериал $$$10$$$ минут, глупеет до $$$s=5*0.9=4.5$$$ и тратит на решение $$$5/s=5/4.5$$$, что примерно составляет $$$1.111$$$ минуты;
  3. Наконец, он хочет решить $$$2$$$-ю задачу: смотрит сериал $$$10$$$ минут, глупеет до $$$s=4.5*0.9=4.05$$$ и тратит на решение $$$20/s=20/4.05$$$, что примерно составляет $$$4.938$$$ минуты.

Таким образом, Поликарп может потратить примерно $$$4+10+1.111+10+4.938=30.049$$$ минут, чтобы набрать $$$7$$$ баллов. Действуя любым другим способом, набрать больше баллов за $$$31$$$ минуту он не успеет.

Во втором примере набрать $$$20$$$ баллов Поликарп может следующим образом:

  1. Сначала он тренируется $$$4$$$ минуты, увеличивая $$$s$$$ до величины $$$5$$$;
  2. Потом хочет решить $$$1$$$-ю задачу: смотрит сериал $$$10$$$ минут, глупеет до $$$s=5*0.9=4.5$$$ и тратит на решение $$$1/s=1/4.5$$$, что примерно составляет $$$0.222$$$ минуты;
  3. Наконец, он хочет решить $$$2$$$-ю задачу: смотрит сериал $$$10$$$ минут, глупеет до $$$s=4.5*0.9=4.05$$$ и тратит на решение $$$10/s=10/4.05$$$, что примерно составляет $$$2.469$$$ минуты.

Таким образом, Поликарп может потратить примерно $$$4+10+0.222+10+2.469=26.691$$$ минут, чтобы набрать $$$20$$$ баллов. Действуя любым другим способом, набрать больше баллов за $$$30$$$ минут он не успеет.