TVShow problem

import java.io.*;
import java.util.*;

public class TV {

    class TVShow {
        int id;
        int a, b, type;

        TVShow(int id, int type, int a, int b) {
            this.id = id;
            this.a = a;
            this.b = b;
            this.type = type;
        }
    }

    int[] getPartitionCost(ArrayList<TVShow> a) {
        int n = a.size();
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 0; i < n + 1; i++)
            Arrays.fill(dp[i], Integer.MIN_VALUE / 3);
        dp[0][0] = 0;
        for (int i = 0; i < n; i++)
            for (int nowGroups = 0; nowGroups <= n; nowGroups++)
                if (dp[nowGroups][i] != Integer.MIN_VALUE / 3) {
                    dp[nowGroups][i + 1] = Math.max(dp[nowGroups][i + 1],
                            dp[nowGroups][i]);
                    dp[nowGroups][i + 1] = Math.max(dp[nowGroups][i + 1],
                            dp[nowGroups][i] + a.get(i).a);
                    dp[nowGroups + 1][i + 1] = Math.max(
                            dp[nowGroups + 1][i + 1],
                            dp[nowGroups][i] + a.get(i).b);
                }
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++)
            res[i] = dp[i][n];
        res[0] = 0;
        return res;
    }

    int[] getAnsForSomeType(ArrayList<TVShow> a, int needGroups) {
        if (needGroups == 0) {
            return new int[] {};
        }
        int n = a.size();
        int[][] dp = new int[n + 1][n + 1];
        int[][] lastTypeDp = new int[n + 1][n + 1];
        // 0 = not used
        // 1 = +a
        // 2 = +b
        for (int i = 0; i < n + 1; i++)
            Arrays.fill(dp[i], Integer.MIN_VALUE / 3);
        dp[0][0] = 0;
        for (int i = 0; i < n; i++)
            for (int nowGroups = 0; nowGroups <= n; nowGroups++)
                if (dp[nowGroups][i] != Integer.MIN_VALUE / 3) {
                    if (dp[nowGroups][i] > dp[nowGroups][i + 1]) {
                        dp[nowGroups][i + 1] = Math.max(dp[nowGroups][i + 1],
                                dp[nowGroups][i]);
                        lastTypeDp[nowGroups][i + 1] = 0;
                    }
                    if (dp[nowGroups][i] + a.get(i).a > dp[nowGroups][i + 1]) {
                        dp[nowGroups][i + 1] = Math.max(dp[nowGroups][i + 1],
                                dp[nowGroups][i] + a.get(i).a);
                        lastTypeDp[nowGroups][i + 1] = 1;
                    }
                    if (dp[nowGroups][i] + a.get(i).b > dp[nowGroups + 1][i + 1]) {
                        dp[nowGroups + 1][i + 1] = Math.max(
                                dp[nowGroups + 1][i + 1],
                                dp[nowGroups][i] + a.get(i).b);
                        lastTypeDp[nowGroups + 1][i + 1] = 2;
                    }
                }
        ArrayList<Integer> usedAsA = new ArrayList<>();
        ArrayList<Integer> usedAsB = new ArrayList<>();
        for (int i = n; i > 0; i--) {
            if (lastTypeDp[needGroups][i] == 0) {
                // nothing to do here
            } else {
                if (lastTypeDp[needGroups][i] == 1) {
                    usedAsA.add(a.get(i - 1).id);
                } else {
                    usedAsB.add(a.get(i - 1).id);
                    needGroups--;
                }
            }
        }
        int[] res = new int[usedAsA.size() + usedAsB.size()];
        for (int i = 0; i < usedAsB.size(); i++) {
            res[i] = usedAsB.get(i);
        }
        for (int i = 0; i < usedAsA.size(); i++) {
            res[i + usedAsB.size()] = usedAsA.get(i);
        }
        return res;
    }

    void printAns(int biggestGroup) {
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++)
            Arrays.fill(dp[i], Integer.MIN_VALUE / 3);
        dp[0][0] = 0;
        for (int type = 0; type < n; type++) {
            for (int wasCount = 0; wasCount <= n; wasCount++)
                if (dp[type][wasCount] != Integer.MIN_VALUE / 3) {
                    for (int newGroupSize = 0; newGroupSize < Math.min(
                            biggestGroup + 1, partitionCost[type].length); newGroupSize++) {
                        dp[type + 1][wasCount + newGroupSize] = Math.max(
                                dp[type + 1][wasCount + newGroupSize],
                                dp[type][wasCount]
                                        + partitionCost[type][newGroupSize]);
                    }
                }
        }
        int best = 0, bestTotal = -1;
        for (int totalGroupsCount = biggestGroup * 2 - 1; totalGroupsCount <= n; totalGroupsCount++) {
            int cost = dp[n][totalGroupsCount];
            if (cost > best) {
                best = cost;
                bestTotal = totalGroupsCount;
            }
        }
        int[] needSomeType = new int[n];
        for (int type = n; type > 0; type--) {
            for (int newGroupSize = 0; newGroupSize < Math.min(
                    biggestGroup + 1, partitionCost[type - 1].length); newGroupSize++) {
                if (bestTotal - newGroupSize >= 0) {
                    if (dp[type - 1][bestTotal - newGroupSize]
                            + partitionCost[type - 1][newGroupSize] == dp[type][bestTotal]) {
                        needSomeType[type - 1] = newGroupSize;
                        bestTotal -= newGroupSize;
                        break;
                    }
                }
            }
        }
        int[][] resultForSomeType = new int[n][];
        for (int i = 0; i < n; i++) {
            resultForSomeType[i] = getAnsForSomeType(ofSomeType[i],
                    needSomeType[i]);
        }
        ArrayList<Integer>[] groups = new ArrayList[biggestGroup];
        for (int i = 0; i < groups.length; i++)
            groups[i] = new ArrayList<>();
        int iter = 0;
        for (int type = 0; type < n; type++) {
            if (needSomeType[type] == biggestGroup) {
                for (int j = 0; j < needSomeType[type]; j++) {
                    groups[j].add(resultForSomeType[type][j]);
                }
                for (int j = needSomeType[type]; j < resultForSomeType[type].length; j++)
                    groups[0].add(resultForSomeType[type][j]);
            }
        }
        for (int type = 0; type < n; type++) {
            if (needSomeType[type] != biggestGroup) {
                int fIter = iter;
                for (int j = 0; j < needSomeType[type]; j++) {
                    groups[iter].add(resultForSomeType[type][j]);
                    iter++;
                    if (iter >= biggestGroup - 1)
                        iter = 0;
                }
                for (int j = needSomeType[type]; j < resultForSomeType[type].length; j++)
                    groups[fIter].add(resultForSomeType[type][j]);
            }
        }
        ArrayList<Integer> result = new ArrayList<>();
        for (int group = 0; group < groups.length; group++)
            for (int x : groups[group])
                result.add(x);
        out.println(result.size());
        for (int i = 0; i < result.size(); i++) {
            out.print((result.get(i)) + " ");
        }
        out.println();
    }

    int n;
    int[][] partitionCost;
    ArrayList<TVShow>[] ofSomeType;

    void solve() {
        n = in.nextInt();
        TVShow[] a = new TVShow[n];
        for (int i = 0; i < n; i++) {
            a[i] = new TVShow(i + 1, in.nextInt() - 1, in.nextInt(),
                    in.nextInt());
        }
        ofSomeType = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            ofSomeType[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            ofSomeType[a[i].type].add(a[i]);
        }
        partitionCost = new int[n][];
        for (int i = 0; i < n; i++) {
            partitionCost[i] = getPartitionCost(ofSomeType[i]);
        }
        int bestAns = 0;
        int bestBiggestGroupSize = -1;
        for (int biggestGroup = 1; biggestGroup <= n; biggestGroup++) {
            int[][] dp = new int[n + 1][n + 1];
            for (int i = 0; i <= n; i++)
                Arrays.fill(dp[i], Integer.MIN_VALUE / 3);
            dp[0][0] = 0;
            for (int type = 0; type < n; type++) {
                for (int wasCount = 0; wasCount <= n; wasCount++)
                    if (dp[type][wasCount] != Integer.MIN_VALUE / 3) {
                        for (int newGroupSize = 0; newGroupSize < Math.min(
                                biggestGroup + 1, partitionCost[type].length); newGroupSize++) {
                            dp[type + 1][wasCount + newGroupSize] = Math
                                    .max(dp[type + 1][wasCount + newGroupSize],
                                            dp[type][wasCount]
                                                    + partitionCost[type][newGroupSize]);
                        }
                    }
            }
            for (int totalGroupsCount = biggestGroup * 2 - 1; totalGroupsCount <= n; totalGroupsCount++) {
                int cost = dp[n][totalGroupsCount];
                if (cost > bestAns) {
                    bestAns = cost;
                    bestBiggestGroupSize = biggestGroup;
                }
            }
        }
        if (bestAns == 0) {
            out.println("0 0");
            return;
        }
        out.print(bestAns + " ");
        printAns(bestBiggestGroupSize);
    }

    InputReader in;
    PrintWriter out;

    void runIO() {
        in = new InputReader(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    void run() {
        in = new InputReader(new File("input.txt"));
        try {
            out = new PrintWriter(new File("output.txt"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        solve();

        out.close();
    }

    public static void main(String[] args) {
        new TV().runIO();
    }

    class InputReader {
        BufferedReader bf;
        StringTokenizer st;

        InputReader(File f) {
            try {
                bf = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        InputReader(InputStream s) {
            bf = new BufferedReader(new InputStreamReader(s));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                String s;
                try {
                    s = bf.readLine();
                } catch (IOException e) {
                    return null;
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

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

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

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

        boolean hasMoreElements() {
            while (!st.hasMoreElements()) {
                String s;
                try {
                    s = bf.readLine();
                } catch (IOException e) {
                    return false;
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }
    }
}