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.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * 4 4
 * 1 5 3 4
 * 1 2
 * 1 3
 * 2 3
 * 3 3
 *
 *
 * @author pttrung
 */
public class A {

    public static long Mod = (long) (1e9) + 7;
    static int time = 0;
    static int[][] dp;
    static boolean[][] check;

    public static void main(String[] args) throws FileNotFoundException {
        PrintWriter out = new PrintWriter(System.out);
        Scanner in = new Scanner();

        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        int[][][] data = new int[n][m][3];
        for (int i = 0; i < n; i++) {
            in.next();
            for (int j = 0; j < m; j++) {
                data[i][j][0] = in.nextInt();//buy
                data[i][j][1] = in.nextInt();//sell
                data[i][j][2] = in.nextInt();//num
            }
        }
        dp = new int[m][k + 1];
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    check = new boolean[m][k + 1];
                    int tmp = cal(0, k, i, j, data);
                    result = Math.max(tmp, result);
                }
            }
        }
        out.println(result);
        out.close();
    }

    static int cal(int index, int left, int buy, int sell, int[][][] data) {
        if (index == data[buy].length) {
            return 0;
        }
        if (left == 0) {
            return 0;
        }
        if (check[index][left] ) {
            return dp[index][left];
        }
        check[index][left] = true;
        int result = 0;
        if (data[buy][index][0] < data[sell][index][1]) {
            for (int i = 1; i <= Math.min(left, data[buy][index][2]); i++) {
                int tmp = (data[sell][index][1] - data[buy][index][0]) * i + cal(index + 1, left - i, buy, sell, data);
                result = Math.max(result, tmp);
            }
        }
        result = Math.max(result, cal(index + 1, left, buy, sell, data));
        return dp[index][left] = result;
    }

    static long squareDist(int x, int y) {
        long X = x;
        long Y = y;
        return X * X + Y * Y;
    }

    static int find(int index, int[] u) {
        if (index != u[index]) {
            return u[index] = find(u[index], u);
        }
        return index;
    }

    public static long pow(int a, int b, long mod) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        long v = pow(a, b / 2, mod);
        if (b % 2 == 0) {
            return (v * v) % mod;
        } else {
            return (((v * v) % mod) * a) % mod;
        }
    }

    public static int[][] powSquareMatrix(int[][] A, long p) {
        int[][] unit = new int[A.length][A.length];
        for (int i = 0; i < unit.length; i++) {
            unit[i][i] = 1;
        }
        if (p == 0) {
            return unit;
        }
        int[][] val = powSquareMatrix(A, p / 2);
        if (p % 2 == 0) {
            return mulMatrix(val, val);
        } else {
            return mulMatrix(A, mulMatrix(val, val));
        }

    }

    public static int[][] mulMatrix(int[][] A, int[][] B) {
        int[][] result = new int[A.length][B[0].length];
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[0].length; j++) {
                long temp = 0;
                for (int k = 0; k < A[0].length; k++) {

                    temp += ((long) A[i][k] * B[k][j] % Mod);
                    temp %= Mod;
                }
                temp %= Mod;
                result[i][j] = (int) temp;
            }
        }

        return result;
    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;




    }

    static class FT {

        int[] data;

        FT(int n) {
            data = new int[n];
        }

        void update(int index, int val) {
            // System.out.println("UPDATE INDEX " + index);
            while (index < data.length) {
                data[index] += val;
                index += index & (-index);

                //    System.out.println("NEXT " +index);
            }
        }

        int get(int index) {
            //  System.out.println("GET INDEX " + index);
            int result = 0;
            while (index > 0) {
                result += data[index];
                index -= index & (-index);
                // System.out.println("BACK " + index);
            }
            return result;
        }
    }

    static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    static long pow(long a, int b) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        long val = pow(a, b / 2);
        if (b % 2 == 0) {

            return val * val % Mod;
        } else {
            return (val * val % Mod) * a % Mod;
        }
    }

//    static Point intersect(Point a, Point b, Point c) {
//        double D = cross(a, b);
//        if (D != 0) {
//            return new Point(cross(c, b) / D, cross(a, c) / D);
//        }
//        return null;
//    }
//
//    static Point convert(Point a, double angle) {
//        double x = a.x * cos(angle) - a.y * sin(angle);
//        double y = a.x * sin(angle) + a.y * cos(angle);
//        return new Point(x, y);
//    }
    static Point minus(Point a, Point b) {
        return new Point(a.x - b.x, a.y - b.y);
    }
//
//    static Point add(Point a, Point b) {
//        return new Point(a.x + b.x, a.y + b.y);
//    }
//

    /**
     * Cross product ab*ac
     *
     * @param a
     * @param b
     * @param c
     * @return
     */
    static double cross(Point a, Point b, Point c) {
        Point ab = new Point(b.x - a.x, b.y - a.y);
        Point ac = new Point(c.x - a.x, c.y - a.y);
        return cross(ab, ac);
    }

    static double cross(Point a, Point b) {
        return a.x * b.y - a.y * b.x;
    }

    /**
     * Dot product ab*ac;
     *
     * @param a
     * @param b
     * @param c
     * @return
     */
    static long dot(Point a, Point b, Point c) {
        Point ab = new Point(b.x - a.x, b.y - a.y);
        Point ac = new Point(c.x - a.x, c.y - a.y);
        return dot(ab, ac);
    }

    static long dot(Point a, Point b) {
        long total = a.x * b.x;
        total += a.y * b.y;
        return total;
    }

    static double dist(Point a, Point b) {
        long total = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
        return Math.sqrt(total);
    }

    static long norm(Point a) {
        long result = a.x * a.x;
        result += a.y * a.y;
        return result;
    }

    static double dist(Point a, Point b, Point x, boolean isSegment) {
        double dist = cross(a, b, x) / dist(a, b);
        // System.out.println("DIST " + dist);

        if (isSegment) {
            Point ab = new Point(b.x - a.x, b.y - a.y);

            long dot1 = dot(a, b, x);
            long norm = norm(ab);
            double u = (double) dot1 / norm;
            if (u < 0) {
                return dist(a, x);
            }

            if (u > 1) {
                return dist(b, x);
            }
        }
        return Math.abs(dist);




    }

    static long squareDist(Point a, Point b) {
        long x = a.x - b.x;
        long y = a.y - b.y;
        return x * x + y * y;
    }

    static class Point {

        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Point{" + "x=" + x + ", y=" + y + '}';
        }
    }

    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() throws FileNotFoundException {
            //System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
            //br = new BufferedReader(new FileReader(new File("A-large (2).in")));
        }

        public String next() {


            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}
