Задача K6. Импортозамещение ≡

Условие

Страна Битландия производит множество товаров. Соседняя страна Байтландия постоянно закупалась у Битландии.

Недавно в Байтландии произошла эпидемия, из-за которой нарушились каналы для поставки товаров. На восстановление уйдет много времени и денег.

Из-за этого Байтландия запустила тендер на закупку импортозамещающих товаров. Было определено k различных категорий товаров, которые пользуются спросом в стране. Каждая категория имеет свой код от 1 до k включительно. Свои товары предложили n различных компаний. Они заявили, какой тип товара предоставят, в каком количестве они его поставят и суммарную цену за всю поставку. По условиям тендера каждый товар может быть закуплен только у одной компании.

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

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

В первой строке заданы три натуральных числа n, k и s — количество заявок, количество категорий товаров и минимально необходимое общее количество товаров соответственно.

В следующих n строках записано по три натуральных числа t_i, a_i и c_i — код товара, количество товара и суммарную стоимость соответственно.

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

Выведите одно целое число — минимальную сумма, которую надо потратить на закупку. Если не закупку совершить невозможно, выведите -1.

Ограничения

1 ≤ n ≤ 10⁴

1 ≤ t_i ≤ k ≤ 100

1 ≤ a_i ≤ s ≤ 1000

1 ≤ c ≤ 100

Пояснение к примеру

В первом примере мы можем закупить товары у второй, четвертой и пятой компании. Суммарно мы наберем 8 товаров и заплатим 8 единиц денег.

Примеры тестов

7 5 8
3 2 9
4 2 4
4 4 7
3 2 2
2 4 2
1 4 10
4 3 7

8