import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class KnapsackProblem {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    //-----------------------------------------------------------------------------------------------------------01背包问题

    /**
     * 这里的f[i][j]表示的取前i个物品且物品体积不大于V的最大体积
     *
     * @param goods
     * @param V
     * @return
     */
    public static int knapsack01(List<int[]> goods, int V) {
        int N = goods.size();
        int[][] f = new int[N + 1][V + 1];
        for (int i = 1; i <= N; i++) {
            int[] good = goods.get(i - 1);
            for (int j = 0; j <= V; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= good[0]) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - good[0]] + good[1]);
                }
            }
        }
        return f[N][V];
    }

    /**
     * 01背包优化
     *
     * @param goods
     * @param V
     * @return
     */
    public static int knapsack01Better(List<int[]> goods, int V) {
        int N = goods.size();
        int[] f = new int[V + 1];
        for (int i = 1; i <= N; i++) {
            int[] good = goods.get(i - 1);
            for (int j = V; j >= good[0]; j--) {
                f[j] = Math.max(f[j], f[j - good[0]] + good[1]);
            }
        }
        return f[V];
    }


    //-----------------------------------------------------------------------------------------------------------完全背包问题

    /**
     * 完全背包问题朴素解法
     *
     * @param goods
     * @param V
     * @return
     */
    public static int knapsackFull(List<int[]> goods, int V) {
        int N = goods.size();
        int[][] f = new int[N + 1][V + 1];
        for (int i = 1; i <= N; i++) {
            int[] good = goods.get(i - 1);
            for (int j = 0; j <= V; j++) {
                for (int k = 0; k * good[0] <= j; k++) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k * good[0]] + k * good[1]);
                }
            }
        }
        return f[N][V];
    }

    /**
     * 优化
     *
     * @param goods
     * @param V
     * @return
     */
    public static int knapsackFullBetter(List<int[]> goods, int V) {
        int N = goods.size();
        int[][] f = new int[N + 1][V + 1];
        for (int i = 1; i <= N; i++) {
            int[] good = goods.get(i - 1);
            for (int j = 0; j <= V; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= good[0]) {
                    f[i][j] = Math.max(f[i][j], f[i][j - good[0]] + good[1]);
                }
            }
        }
        return f[N][V];
    }

    /**
     * 在优化
     *
     * @param goods
     * @param V
     * @return
     */
    public static int knapsackFullBetterBetter(List<int[]> goods, int V) {
        int N = goods.size();
        int[] f = new int[V + 1];
        for (int i = 1; i <= N; i++) {
            int[] good = goods.get(i - 1);
            for (int j = good[0]; j <= V; j++) {
                f[j] = Math.max(f[j], f[j - good[0]] + good[1]);
            }
        }
        return f[V];
    }


    //-----------------------------------------------------------------------------------------------------------完全背包问题

    /**
     * 多重背包问题
     *
     * @param goods
     * @param V
     * @return
     */
    public static int knapsackMultiple(List<int[]> goods, int V) {
        int N = goods.size();
        int[][] f = new int[N + 1][V + 1];
        for (int i = 1; i <= N; i++) {
            int[] good = goods.get(i - 1);
            for (int j = 0; j <= V; j++) {
                for (int k = 0; k <= good[2] && k * good[0] <= j; k++) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k * good[0]] + k * good[1]);
                }
            }
        }
        return f[N][V];
    }

    /**
     * 二进制优化
     *
     * @param goods
     * @param V
     * @return
     */
    public static int knapsackMultipleBetter(List<int[]> goods, int V) {
        List<int[]> theGoods = new ArrayList<>();
        for (int[] good : goods) {
            int s = good[2];
            int k = 1;
            while (s >= k) {
                theGoods.add(new int[]{k * good[0], k * good[1]});
                s -= k;
                k <<= 1;
            }
            if (s > 0) {
                theGoods.add(new int[]{s * good[0], s * good[1]});
            }
        }
        int[] f = new int[V + 1];
        int n = theGoods.size();
        return knapsack01Better(theGoods, V);
    }

    //-----------------------------------------------------------------------------------------------------------分组背包问题

    /**
     * 分组背包问题
     *
     * @param goods
     * @param V
     * @return
     */
    public static int knapsackGroup(List<List<int[]>> goods, int V) {
        int n = goods.size();
        int[] f = new int[V + 1];
        for (int i = 1; i <= n; i--) {
            List<int[]> theGoods = goods.get(i - 1);
            for (int j = V; j >= 0; j++) {
                for (int[] good : theGoods) {
                    if (good[0] <= j) {
                        f[j] = Math.max(f[j], f[j - good[0]] + good[1]);
                    }
                }
            }
        }
        return f[V];
    }

    public static List<int[]> getGoods(int N, boolean flag) {
        List<int[]> goods = new ArrayList<>();
        try {
            while (N-- != 0) {
                String[] arg = br.readLine().split(" ");
                if (flag) {
                    goods.add(new int[]{Integer.parseInt(arg[0]), Integer.parseInt(arg[1])});
                } else {
                    goods.add(new int[]{Integer.parseInt(arg[0]), Integer.parseInt(arg[1]), Integer.parseInt(arg[2])});
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        return goods;
    }

    public static void test1() {
        try {
            String[] arg = br.readLine().split(" ");
            int N = Integer.parseInt(arg[0]), V = Integer.parseInt(arg[1]);
            List<int[]> goods = getGoods(N, true);
            System.out.println(knapsack01(goods, V));
            System.out.println(knapsack01Better(goods, V));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void test2() {
        try {
            String[] arg = br.readLine().split(" ");
            int N = Integer.parseInt(arg[0]), V = Integer.parseInt(arg[1]);
            List<int[]> goods = getGoods(N, true);
            System.out.println(knapsackFull(goods, V));
            System.out.println(knapsackFullBetter(goods, V));
            System.out.println(knapsackFullBetterBetter(goods, V));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void test3() {
        try {
            String[] arg = br.readLine().split(" ");
            int N = Integer.parseInt(arg[0]), V = Integer.parseInt(arg[1]);
            List<int[]> goods = getGoods(N, false);
            System.out.println(knapsackMultiple(goods, V));
            System.out.println(knapsackMultipleBetter(goods, V));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void test4() {
        try {
            String[] arg = br.readLine().split(" ");
            int n = Integer.parseInt(arg[0]), v = Integer.parseInt(arg[1]);
            List<List<int[]>> goods = new ArrayList<>();
            while (n-- != 0) {
                int N = Integer.parseInt(br.readLine());
                List<int[]> good = new ArrayList<>();
                while (N-- != 0) {
                    arg = br.readLine().split(" ");
                    good.add(new int[]{Integer.parseInt(arg[0]), Integer.parseInt(arg[1])});
                }
                goods.add(good);
            }
            System.out.println(knapsackGroup(goods, v));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        test1();
        test2();
        test3();
        test4();
    }
}