Выбрать набор снеков с заданной суммарной массой кофеина и минимальным количеством различных типов

Иногда дедлайн подкрадывается незаметно, и, чтобы успеть закончить задачу вовремя, приходится работать целую ночь. Чтобы поддерживать себя в бодрствующем состоянии, проще всего
выпить кофе.
Программист Лев из VK обычно справляется со всеми поставленными задачами заранее, но в
этот раз слишком долго откладывал последнее дело, и планирует закончить его этой ночью. Чтобы
оставаться бодрым, ему необходимо минимум x кофеина. Для этого он собирается собрать комплект
из кофейных снеков, всегда доступных в офисе.
Всего доступно n снеков, i-й из которых присутствует в наличии в массе mi и с долей содержания
кофеина ki%. При этом i-й из снеков имеет тип (напиток, печенье, шоколадный батончик, и т. д.),
характеризующийся целым числом ti
.
Смешивать снеки разных типов плохо, поэтому Лев хочет обойтись как можно меньшим количеством разных типов снеков. Помогите ему выбрать такой набор снеков, суммарная масса кофеина
в котором хотя бы x, а количество различных типов снеком минимально.
Формат входных данных
В первой строке ввода через пробел даны три целых числа n, q и x — число разных снеков, количество типов снеков и необходимая масса кофеина, соответственно (1 6 q 6 n 6 2 · 105
; 1 6 x 6 109
).
В i-й из следующих строк через пробел даны три целых числа ti
, mi и ki — тип, суммарная масса
и процентное содержание кофеина i-го снека (1 6 ti 6 q; 1 6 mi 6 109
; 0 6 ki 6 100).
Формат выходных данных
В единственной строке выведите одно целое число — минимальное необходимое число типов
снеков, необходимое, чтобы набрать x кофеина. Если получить x кофеина, даже взяв все снеки,
невозможно, выведите «-1» (без кавычек).

ввод:
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

0