/* vim: set expandtab tabstop=4 shiftwidth=4 : */

import java.util.HashMap;

public class BaseballElimination
{
    private static final boolean DEBUG = false;

    private int n;
    private String[] names;
    private int[] wins;
    private int[] losses;
    private int[] remains;
    private int[][] games;
    private HashMap<String, Integer> nameToI;
    private boolean[] eliminated;
    private HashMap<Integer, Stack<String>> eliminatedBy;

    public BaseballElimination(String filename)
    {
        In in = new In(filename);

        n = in.readInt();

        names = new String[n];
        wins = new int[n];
        losses = new int[n];
        remains = new int[n];
        games = new int[n][n];
        nameToI = new HashMap<String, Integer>();
        eliminated = new boolean[n];
        eliminatedBy = new HashMap<Integer, Stack<String>>();

        for (int i = 0; i < n; i++) {
            names[i] = in.readString();
            wins[i] = in.readInt();
            losses[i] = in.readInt();
            remains[i] = in.readInt();
            for (int j = 0; j < n; j++) {
                games[i][j] = in.readInt();
            }
            nameToI.put(names[i], i);
        }

        trivialEliminations();

        for (int i = 0; i < n; i++) {
            // if (!eliminated[i] && shouldBeEliminated(i)) {
            if (!eliminated[i]) {
                maxFlowComputation(i);
            }
        }
    }

    private void addEliminatedBy(int who, int by)
    {
        Stack<String> s = eliminatedBy.get(who);
        if (s == null) {
            s = new Stack<String>();
            s.push(names[by]);
            eliminatedBy.put(who, s);
        } else {
            s.push(names[by]);
        }
    }

    private void trivialEliminations()
    {
        // even if the team wins all its remaining games
        // it won't catch up with the best teams
        for (int i = 0; i < n; i++) {
            int w = wins[i] + remains[i];
            for (int j = 0; j < n; j++) {
                // (i == j) is safe
                if (w < wins[j]) {
                    eliminated[i] = true;
                    addEliminatedBy(i, j);
                }
            }
        }
    }

    private boolean shouldBeEliminated(int t)
    {
        // even if the team wins all its remaining games
        // it won't catch up with the min of the others wins
        int w = wins[t] + remains[t];
        int ws = 0;
        for (int i = 0; i < n; i++) {
            if (i == t) continue;
            ws += wins[i];
            for (int j = i; j < n; j++) {
                if (j == t) continue;
                ws += games[i][j];
            }
        }
        if (w < Math.ceil(ws / (float) (n-1))) {
            return true;
        }
        return false;
    }

    private int countGamesWithout(int t)
    {
        int c = 0;
        for (int i = 0; i < n; i++) {
            if (i == t) continue;
            for (int j = i; j < n; j++) {
                if (j == t) continue;
                if (games[i][j] > 0) c++;
            }
        }

        return c;
    }

    private void maxFlowComputation(int t)
    {
        int g = countGamesWithout(t);
        // s + t + games + teams
        int vertices = 2 + g + n;

        FlowNetwork flowNetwork = new FlowNetwork(vertices);

        int S = vertices - 2;
        int T = vertices - 1;
        int idx = n;
        int b = wins[t] + remains[t];
        for (int i = 0; i < n; i++) {
            if (i == t) continue;
            // team -> T
            FlowEdge e = new FlowEdge(i, T, (b - wins[i]));
            flowNetwork.addEdge(e);
            for (int j = i; j < n; j++) {
                if (j == t) continue;
                if (games[i][j] > 0) {
                    // S -> game
                    e = new FlowEdge(S, idx, games[i][j]);
                    flowNetwork.addEdge(e);
                    // game -> team i
                    e = (new FlowEdge(idx, i, Double.POSITIVE_INFINITY));
                    flowNetwork.addEdge(e);
                    // game -> team j
                    e = (new FlowEdge(idx, j, Double.POSITIVE_INFINITY));
                    flowNetwork.addEdge(e);
                    idx++;
                }
            }
        }

        if (DEBUG) {
            System.out.println(names[t]+" should be out…");
            System.out.println(flowNetwork.toString());
        }

        FordFulkerson maxFlow = new FordFulkerson(flowNetwork, S, T);

        if (DEBUG) {
            System.out.println(flowNetwork.toString());
            System.out.printf("Team: %s got :%g \n", names[t], maxFlow.value());
        }

        boolean out = false;
        for (FlowEdge e : flowNetwork.adj(S)) {
            if (DEBUG) System.out.println(e);
            if (e.flow() != e.capacity()) {
                out = true;
                break;
            }
        }

        if (out) {
            eliminated[t] = true;
            for (int i = 0; i < n; i++) {
                if (maxFlow.inCut(i) && !eliminated[i]) {
                    addEliminatedBy(t, i);
                }
            }
        }
    }

    private int teamI(String team)
    {
        Object i = nameToI.get(team);
        if (i == null)
            throw new IllegalArgumentException(team);

        return (int) i;
    }

    public int numberOfTeams()
    {
        return n;
    }

    public Iterable<String> teams()
    {
        return nameToI.keySet();
    }

    public int wins(String team)
    {
        return wins[teamI(team)];
    }

    public int losses(String team)
    {
        return losses[teamI(team)];
    }

    public int remaining(String team)
    {
        return remains[teamI(team)];
    }

    public int against(String team1, String team2)
    {
        return games[teamI(team1)][teamI(team2)];
    }

    public boolean isEliminated(String team)
    {
        return eliminated[teamI(team)];
    }

    public Iterable<String> certificateOfElimination(String team)
    {
        int t = teamI(team);

        if (!eliminated[t])
            return null;
        else {
            return eliminatedBy.get(t);
        }
    }

    public static void main(String[] args) {
        BaseballElimination division = new BaseballElimination(args[0]);
        for (String team : division.teams()) {
            if (division.isEliminated(team)) {
                StdOut.print(team + " is eliminated by the subset R = { ");
                for (String t : division.certificateOfElimination(team))
                    StdOut.print(t + " ");
                StdOut.println("}");
            }
            else {
                StdOut.println(team + " is not eliminated");
            }
        }
    }
}