/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2009 by Doina Logofatu
************************************************/

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

public class P04Triangle {

  private static final String FileInputName = "dreieck.in";
  private static final String FileOutputName = "dreieck.out";

  static void process(int a[][], int n, int s[][], int vPred[][], int w[]) {
    s[0][0] = a[0][0];
    vPred[0][0] = -1;
    for (int i = 1; i < n; i++) {
      s[i][0] = a[i][0] + s[i - 1][0];
      vPred[i][0] = 1;
      for (int j = 1; j <= i; j++) {
        if (s[i - 1][j - 1] >= s[i - 1][j]) {
          vPred[i][j] = 0;
          s[i][j] = a[i][j] + s[i - 1][j - 1];
        } else {
          vPred[i][j] = 1;
          s[i][j] = a[i][j] + s[i - 1][j];
        }
      }
    }
    w[n - 1] = 0;
    for (int j = 0; j <= n - 1; j++)
      if (s[n - 1][j] > s[n - 1][w[n - 1]]) {
        w[n - 1] = j;
      }
    for (int i = n - 2; i >= 0; i--) {
      if (vPred[i + 1][w[i + 1]] == 0)
        w[i] = w[i + 1] - 1;
      else
        w[i] = w[i + 1];
    }
  }

  static void writeData(PrintStream out, int s[][], int w[], int n) {
    out.print(" Maximale Summe = ");
    out.println(s[n - 1][w[n - 1]]);
    for (int i = 0; i < n; i++) {
      out.println(w[i] + 1);
    }
  }

  public static void main(String[] args) throws IOException {
    Scanner scanner = null;
    PrintStream out = null;
    try {
      scanner = new Scanner(new File(FileInputName));
      if (!scanner.hasNext())
        return;
      int n = scanner.nextInt();
      int a[][] = new int[n][];
      int s[][] = new int[n][];
      int vPred[][] = new int[n][];
      int w[] = new int[n];
      for (int i = 0; i < n; i++) {
        a[i] = new int[i + 1];
        s[i] = new int[n];
        vPred[i] = new int[i + 1];
        for (int j = 0; j <= i; j++) {
          if (!scanner.hasNext())
            return;
          a[i][j] = scanner.nextInt();
        }
      }
      process(a, n, s, vPred, w);
      out = new PrintStream(new File(FileOutputName));
      writeData(out, s, w, n);
    } finally {
      if (scanner != null) {
        scanner.close();
      }
      if (out != null) {
        out.close();
      }
    }
  }
}