MODULE MaxZbir;

  FROM IO IMPORT
    WrStr, WrLn, WrCard, WrInt, RdCard, RdInt;

  CONST
    Max = 100;

  VAR
    A, B: ARRAY [1 .. Max], [1 .. Max] OF INTEGER;
    m, n: CARDINAL;
    (* B[vr, ko] je vrednost optimalnog resenja od (1, 1) do (vr, ko) *)

  PROCEDURE Unos;
    VAR
      i, j: CARDINAL;
  BEGIN
    WrStr('Unesite n: ');
    n:= RdCard();
    WrStr('Unesite m: ');
    m:= RdCard();
    IF (n < Max) AND (m < Max) THEN
      FOR i:= 1 TO m DO
        FOR j:= 1 TO n DO
          WrStr('A[');
          WrCard(i, 1);
          WrStr(', ');
          WrCard(j, 1);
          WrStr('] = ');
          A[i, j] := RdInt();
        END;
      END;
    END;
  END Unos;

  PROCEDURE Resi;
    VAR
      i, j: CARDINAL;
  BEGIN
    B[1, 1]:= A[1, 1];
    FOR j:= 2 TO n DO
      B[1, j]:= A[1, j] + B[1, j-1];
    END;
    FOR i:= 2 TO m DO
      B[i, 1]:= A[i, 1] + B[i-1, 1];
    END;
    FOR i:= 2 TO m DO
      FOR j:= 2 TO n DO
        IF B[i, j - 1] < B[i - 1, j] THEN
          B[i, j]:= A[i, j] + B[i - 1, j];
        ELSE
          B[i, j]:= A[i, j] + B[i, j - 1];
        END;
      END;
    END;
  END Resi;

  PROCEDURE Ispis(Vr, Ko: CARDINAL);
    VAR
      i: CARDINAL;
  BEGIN
    IF (Vr > 1) AND (Ko > 1) THEN
      IF B[Vr - 1, Ko] > B[Vr, Ko - 1] THEN
        Ispis(Vr - 1, Ko);
      ELSE
        Ispis(Vr, Ko - 1);
      END;
      WrStr('(');
      WrCard(Vr, 1);
      WrStr(', ');
      WrCard(Ko, 1);
      WrStr(')');
    ELSIF Vr = 1 THEN
      FOR i:= 1 TO Ko DO
        WrStr('(1, ');
        WrCard(i, 1);
        WrStr(')');
      END;
    ELSE
      FOR i:= 1 TO Vr DO
        WrStr('(');
        WrCard(i, 1);
        WrStr(', 1)');
      END;
    END;
  END Ispis;

BEGIN
  Unos;
  IF (n < Max) AND (m < Max) THEN
    Resi;
    WrStr('Maksimalni zbir je ');
    WrInt(B[m, n], 1);
    WrStr(' a postize se ovako:');
    WrLn;
    Ispis(m, n)
  ELSE
    WrStr('Suvise velika matrica.')
  END
END MaxZbir.