A. Торговое дело
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Всего в системе n планет, на каждой из которых можно купить или продать товары m типов (например, продовольствие, медикаменты, оружие, алкоголь и так далее). Для каждой планеты i и каждого типа товара j известны:

  • aij — стоимость покупки единицы товара;
  • bij — стоимость продажи единицы товара;
  • cij — количество оставшихся единиц товара.

Считается, что на планете i можно купить не более cij единиц товара типа j, однако продать можно всегда любое количество товаров любого типа.

Зная, что трюм корабля Йцукена вмещает не более k единиц товаров, определите наибольшее количество прибыли, которое Йцукен может получить.

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

В первой строке записаны через пробел три целых числа n, m и k (2 ≤ n ≤ 10, 1 ≤ m, k ≤ 100) — количество планет, количество типов товаров и размер трюма Йцукена, соответственно.

Далее идут n блоков с описанием каждой планеты.

В первой строке i-ого блока находится название планеты — строка длиной от 1 до 10 латинских букв. Первая буква названия — большая, остальные — маленькие. Далее в i-ом блоке идут m строк, j-ая из них содержит три целых числа aij, bij и cij (1 ≤ bij < aij ≤ 1000, 0 ≤ cij ≤ 100) — числа, описывающие денежные операции с j-м товаром на i-й планете. Числа в строках разделяются пробелами.

Гарантируется, что названия всех планет различны.

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

Выведите одно число — наибольшее количество прибыли, которое можно получить.

Примеры
Входные данные
3 3 10
Venus
6 5 3
7 6 5
8 6 10
Earth
10 9 0
8 6 4
10 9 3
Mars
4 3 0
8 4 12
7 2 5
Выходные данные
16
Примечание

В первом тестовом примере нужно прилететь на планету Venus взять там кредит на 74 денежных единиц и купить 3 единицы первого товара и 7 единиц третьего товара (3·6 + 7·8 = 74). Далее рейнджер должен прилететь на планету Earth и продать там купленные товары. За них он получит 3·9 + 7·9 = 90, из этих денег нужно отдать 74 за кредит. Получается прибыль равна 16 денежным единицам. В данном примере большую прибыль получить невозможно.