Чтобы раздобыть денег на новый эонический бластер, рейнджер Йцукен решил ненадолго заняться торговлей. Он хочет купить некоторое количество товаров (возможно, ничего не купить) на одной из планет, после чего продать купленные товары уже на другой планете. Обратите внимание, что данная операция не повторяется, то есть продажа и покупка производится ровно один раз. Чтобы осуществить свой план, Йцукен собирается взять в банке кредит, покрывающий все расходы, а по окончании операции возвратить взятые в долг деньги (деньги возвращаются без процентов). При этом Йцукен хочет получить как можно больше прибыли.
Всего в системе n планет, на каждой из которых можно купить или продать товары m типов (например, продовольствие, медикаменты, оружие, алкоголь и так далее). Для каждой планеты i и каждого типа товара j известны:
- aij — стоимость покупки единицы товара;
- bij — стоимость продажи единицы товара;
- cij — количество оставшихся единиц товара.
Считается, что на планете i можно купить не более cij единиц товара типа j, однако продать можно всегда любое количество товаров любого типа.
Зная, что трюм корабля Йцукена вмещает не более k единиц товаров, определите наибольшее количество прибыли, которое Йцукен может получить.
Выходные данные
Выведите одно число — наибольшее количество прибыли, которое можно получить.
Примечание
В первом тестовом примере нужно прилететь на планету Venus взять там кредит на 74 денежных единиц и купить 3 единицы первого товара и 7 единиц третьего товара (3·6 + 7·8 = 74). Далее рейнджер должен прилететь на планету Earth и продать там купленные товары. За них он получит 3·9 + 7·9 = 90, из этих денег нужно отдать 74 за кредит. Получается прибыль равна 16 денежным единицам. В данном примере большую прибыль получить невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|