To get money for a new aeonic blaster, ranger Qwerty decided to engage in trade for a while. He wants to buy some number of items (or probably not to buy anything at all) on one of the planets, and then sell the bought items on another planet. Note that this operation is not repeated, that is, the buying and the selling are made only once. To carry out his plan, Qwerty is going to take a bank loan that covers all expenses and to return the loaned money at the end of the operation (the money is returned without the interest). At the same time, Querty wants to get as much profit as possible.

The system has n planets in total. On each of them Qwerty can buy or sell items of m types (such as food, medicine, weapons, alcohol, and so on). For each planet i and each type of items j Qwerty knows the following:

  * aij — the cost of buying an item; 
  * bij — the cost of selling an item; 
  * cij — the number of remaining items.



It is not allowed to buy more than cij items of type j on planet i, but it is allowed to sell any number of items of any kind.

Knowing that the hold of Qwerty's ship has room for no more than k items, determine the maximum profit which Qwerty can get.

Input

The first line contains three space-separated integers n, m and k (2 ≤ n ≤ 10, 1 ≤ m, k ≤ 100) — the number of planets, the number of question types and the capacity of Qwerty's ship hold, correspondingly.

Then follow n blocks describing each planet.

The first line of the i-th block has the planet's name as a string with length from 1 to 10 Latin letters. The first letter of the name is uppercase, the rest are lowercase. Then in the i-th block follow m lines, the j-th of them contains three integers aij, bij and cij (1 ≤ bij < aij ≤ 1000, 0 ≤ cij ≤ 100) — the numbers that describe money operations with the j-th item on the i-th planet. The numbers in the lines are separated by spaces.

It is guaranteed that the names of all planets are different.

Output

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

Examples

Input

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


Output

16

Note

In the first test case you should fly to planet Venus, take a loan on 74 units of money and buy three items of the first type and 7 items of the third type (3·6 + 7·8 = 74). Then the ranger should fly to planet Earth and sell there all the items he has bought. He gets 3·9 + 7·9 = 90 units of money for the items, he should give 74 of them for the loan. The resulting profit equals 16 units of money. We cannot get more profit in this case.
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;

public class Problem_176A_Trading_Business {

    public static void main(String[] args) throws IOException {

        Reader rs = new Reader();
        int nPlanets = rs.nextInt(), mTypes = rs.nextInt();
        int CAP = Integer.parseInt(rs.readLine().trim());
        int[][][] planetItems = new int[nPlanets][mTypes][3]; // [planet index][item type][0=buy,1=sell,2=qty]
        String x;
        for (int p = 0; p < nPlanets; p++) {
            x = rs.readLine(100); // don't care about string
            for (int i = 0; i < mTypes; i++) {
                planetItems[p][i][0] = rs.nextInt(); // cost to buy
                planetItems[p][i][1] = rs.nextInt(); // sell value
                planetItems[p][i][2] = Integer.parseInt(rs.readLine().trim()); // quantity
            }
        }

        int MaxProfit = 0;
        int[][] item = new int[mTypes][2]; // arary which stores the profit of buying and selling an item and the qantity

        // for each planet pair
        for (int i = 0; i < nPlanets; i++) {
            for (int j = 0; j < nPlanets; j++) {
                if (i != j) { // don't compare a planet with itself
                    for (int k = 0; k < mTypes; k++) {
                        int[] buy = planetItems[i][k]; // item to buy
                        int[] sell = planetItems[j][k]; // item to sell
                        item[k][0] = buy_sell(buy, sell); // value per buy/sell
                        item[k][1] = (item[k][0] < 0) ? 0 : buy[2]; // quantity of item // and do not want to allow negatives
                    }
                    sortbyColumn(item, 0);// sort the items by their gained values (first column) 
                                        // in descending order***

                    
                    int qty = 0, planetI = 0; // counts the number of items bought
                    // iterate from greatest to least
                    for (int k = 0; k < item.length && qty < CAP; k++) { // for each item's profit // while the ship has room
                        for (int q = 0; q < item[k][1] && qty < CAP; q++) {// for the quantity of that item
                            planetI += item[k][0]; // add profit
                            qty++;                 // increment
                        }
                    }
                    MaxProfit = Math.max(MaxProfit, planetI); // store the profit if it was a maximum
                }
            }
        }

        System.out.println(MaxProfit);

    }

    public static int buy_sell(int[] buy, int[] sell) {
        return sell[1] - buy[0]; // sale price minus the purchase price
    }

    public static void sortbyColumn(int arr[][], int col) {
        // Using built-in sort function Arrays.sort
        Arrays.sort(arr, new Comparator<int[]>() {

            @Override
            // Compare values according to columns
            public int compare(final int[] entry1, final int[] entry2) {

                // descending order
                if (entry1[col] < entry2[col])
                    return 1;
                else
                    return -1;
            }
        }); // End of function call sort().
    }

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public String readLine(int length) throws IOException {
            byte[] buf = new byte[length]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }
}
