A. Coffee Cocktail
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Иногда дедлайн подкрадывается незаметно, и, чтобы успеть закончить задачу вовремя, приходится работать целую ночь. Чтобы поддерживать себя в бодрствующем состоянии, проще всего выпить кофе.

Программист Лев из VK обычно справляется со всеми поставленными задачами заранее, но в этот раз слишком долго откладывал последнее дело, и планирует закончить его этой ночью. Чтобы оставаться бодрым, ему необходимо минимум $$$x$$$ кофеина. Для этого он собирается собрать комплект из кофейных снеков, всегда доступных в офисе.

Всего доступно $$$n$$$ снеков, $$$i$$$-й из которых присутствует в наличии в массе $$$m_i$$$ и с долей содержания кофеина $$$k_i \%$$$. При этом $$$i$$$-й из снеков имеет тип (напиток, печенье, шоколадный батончик, и т. д.), характеризующийся целым числом $$$t_i$$$.

Смешивать снеки разных типов плохо, поэтому Лев хочет обойтись как можно меньшим количеством разных типов снеков. Помогите ему выбрать такой набор снеков, суммарная масса кофеина в котором хотя бы $$$x$$$, а количество различных типов снеком минимально.

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

В первой строке ввода через пробел даны три целых числа $$$n$$$, $$$q$$$ и $$$x$$$ — число разных снеков, количество типов снеков и необходимая масса кофеина, соответственно ($$$1 \le q \le n \le 2 \cdot 10^5$$$; $$$1 \le x \le 10^9$$$).

В $$$i$$$-й из следующих строк через пробел даны три целых числа $$$t_i$$$, $$$m_i$$$ и $$$k_i$$$ — тип, суммарная масса и процентное содержание кофеина $$$i$$$-го снека ($$$1 \le t_i \le q$$$; $$$1 \le m_i \le 10^9$$$; $$$0 \le k_i \le 100$$$).

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

В единственной строке выведите одно целое число — минимальное необходимое число типов снеков, необходимое, чтобы набрать $$$x$$$ кофеина. Если получить $$$x$$$ кофеина, даже взяв все снеки, невозможно, выведите «-1» (без кавычек).

Система оценки

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

ПодзадачаБаллыОграниченияНеобходимые подзадачи
0–примеры из условия
112$$$q = 1$$$
216$$$k_i = 100$$$, $$$t_i \ne t_j$$$, $$$m_i = m_j$$$ для всех $$$i$$$, $$$j$$$
318$$$t_i \ne t_j$$$, $$$k_i = k_j$$$ для всех $$$i$$$, $$$j$$$2
417$$$t_i \ne t_j$$$ для всех $$$i$$$, $$$j$$$2, 3
517$$$k_i = k_j$$$ для всех $$$i, j$$$2, 3
620нет0 – 5
Примеры
Входные данные
4 3 10
1 4 25
2 5 100
2 4 100
3 1 10
Выходные данные
2
Входные данные
5 4 3
1 4 50
1 5 20
2 2 50
2 2 25
4 2 100
Выходные данные
1