2.3 BidWiser Hangover

Score: 80pts

Time Limit: 2.00 sec

TSEC CodeCell just got done with its event - BidWiser - brought to you by Rogue Code and Brownie Boulevard. The winners decided to engage in trade for a while.

They want to buy some number of items (or probably not to buy anything at all) in one of the stores and then sell the bought items in another store. Note that this operation is not repeated, that is, the buying and the selling are made only once.

To carry out his plan, they are going to take a bank loan that covers all expenses and return the loaned money at the end of the operation (the money is returned without the interest). At the same time, they want to get as much profit as possible.

They have chosen you as their representative to make all the decisions. But, you have been given a limit to buy no more than k items.

The system has n stores in total. On each of them, you can buy or sell items of m types (such as food, medicine, weapons, alcohol, and so on). For each store and each type of item j, you know the following:

a_ij — the cost of buying an item;

b_ij — the cost of selling an item;

c_ij — the number of remaining items.

Note: It is not allowed to buy more than c_ij items of type j in store i, but it is allowed to sell any number of items of any kind.

Knowing that the limit for purchase is for no more than k items, determine the maximum profit you can get them.

They want to buy some number of items (or probably not to buy anything at all) in one of the stores and then sell the bought items in another store. Note that this operation is not repeated, that is, the buying and the selling are made only once.

To carry out his plan, they are going to take a bank loan that covers all expenses and return the loaned money at the end of the operation (the money is returned without the interest). At the same time, they want to get as much profit as possible.

They have chosen you as their representative to make all the decisions. But, you have been given a limit to buy no more than k items.

The system has n stores in total. On each of them, you can buy or sell items of m types (such as food, medicine, weapons, alcohol, and so on). For each store and each type of item j, you know the following:

a_ij — the cost of buying an item;

b_ij — the cost of selling an item;

c_ij — the number of remaining items.

Note: It is not allowed to buy more than c_ij items of type j in store i, but it is allowed to sell any number of items of any kind.

Knowing that the limit for purchase is for no more than k items, determine the maximum profit you can get them.

Constraints

2 ≤ n ≤ 10

1 ≤ m, k ≤ 100

1 ≤ b_ij < a_ij ≤ 1000

0 ≤ c_ij ≤ 100

1 ≤ m, k ≤ 100

1 ≤ b_ij < a_ij ≤ 1000

0 ≤ c_ij ≤ 100

Input Format

The first line contains three space-separated integers n, m, and k — the number of stores, the number of question types, and the maximum number of items you can buy from that respective store, correspondingly.

The first line of the i-th block has the store's name as a string with length from 1 to 10 letters.

Then in the i-th block follow m lines, the j-th of them contains three integers a_ij, b_ij, and c_ij — the numbers that describe money operations with the j-th item on the i-th store. The numbers in the lines are separated by spaces.

The first line of the i-th block has the store's name as a string with length from 1 to 10 letters.

Then in the i-th block follow m lines, the j-th of them contains three integers a_ij, b_ij, and c_ij — the numbers that describe money operations with the j-th item on the i-th store. The numbers in the lines are separated by spaces.

Output Format

Print a single number — the maximum profit you can get.

Example 1

Input:

3 3 10

Kataria

6 5 3

7 6 5

8 6 10

KcStores

10 9 0

8 6 4

10 9 3

RMart

4 3 0

8 4 12

7 2 5

Output:

16

Explanation:

In the first test case, you should go to store Kataria, take a loan on 74 units of money and buy 3 items of the first type and 7 items of the third type (3·6 + 7·8 = 74).

Then you should go to KcStores and sell all the items you have bought. You get 3·9 + 7·9 = 90 units of money for the items, you should give 74 of them for the loan.

The resulting profit equals 16 units of money.

Note: We cannot get more profit in this case.

3 3 10

Kataria

6 5 3

7 6 5

8 6 10

KcStores

10 9 0

8 6 4

10 9 3

RMart

4 3 0

8 4 12

7 2 5

Output:

16

Explanation:

In the first test case, you should go to store Kataria, take a loan on 74 units of money and buy 3 items of the first type and 7 items of the third type (3·6 + 7·8 = 74).

Then you should go to KcStores and sell all the items you have bought. You get 3·9 + 7·9 = 90 units of money for the items, you should give 74 of them for the loan.

The resulting profit equals 16 units of money.

Note: We cannot get more profit in this case.