{ ID�JA: Jei neb�t� sukeitimo, tai b�t� papras�iausias dinaminio
  programavimo u�davinys. Dabar t� klasikin� sprendimo id�j�
  reikia �iek tiek modifikuoti.

  P.s. Atkreipkite d�mes�, kad n�ra akivaizdu kaip sutalpinti
  vis� eilut� � atmint�. Spr�sdami darome papras�iau. �simename
  tik naujai perskaityt� ir buvusi� eilut�.

  1. Perskaitome pirm�j� eilut�. J� �simename lentel�je eil_nek.

     Jei �ioje eilut�je b�t� atliekamas sukeitimas, tai visus
     jos elementus b�t� galima pakeisti maksmalia reik�me. T� ir padarome.
     Rezultat� �simename lentel�je eil_suk.

  2. Perskaitome tolesn� eilut� eil. Galimi trys variantai.

      a) Sukeitimas iki �iol nebuvo darytas ir nebus daromas
         �ioje eilut�je.

         Tuomet remdamiesi eilut�mis eil bei eil_nek atnaujiname
         eilut� eil_nek, t.y. randame ilgiausius kelius nuo vir�utin�s
         eilut�s iki perskaitytosios eilut�s kiekvieno elemento

     b) Sukeitimas jau buvo padarytas ankstesn�je eilut�je.

         Tuomet remdamiesi eilut�mis eil bei eil_suk atnaujiname
         eilut� eil_suk, t.y. randame ilgiausius kelius nuo vir�utin�s
         eilut�s iki perskaitytosios eilut�s kiekvieno elemento.

     c) Sukeitimas daromas �ioje eilut�je.

        Randame did�iausi� eil element�. Tuomet remdamiesi eilute
        eil_nek atnaujiname eilut� eil_suk.


     Eilut� eil_nek atnaujinama tik atliekant �ingsn� a).
     Tuo tarpu atlikdami b) ir c) �ingsnius gausime dvi eilut�s
     eil_suk versijas. �ias dvi eilutes "sujungiame" pasirinkdami
     didesniuosiu elementus:
        eil_suk_atnaujinta[i] := max(eil_suk_a[i], eil_suk_b[i]);
        i kinta nuo 1 iki eilut�s ilgio.

3. Antr�j� �ingsn� kartojame kol per�i�rime visas eilutes.

4. I�renkame did�iausi� eilu�i� eil_nek ir eil_suk element�. Tai ir bus
   ie�komas kelias.
}
program korio_uzdavinys;

  const PR = 'hon.in';
        RZ = 'hon.out';
        MAX_N = 99;
  type eilute = array [1..2*MAX_N-1] of integer;

  procedure skaityti (var f: text; ilg: integer; var eil: eilute);
    { i� pradini� duomen� bylos perskaito nurodyto ilgio eilut� }
    var i: integer;
  begin
    for i := 1 to ilg do
      read (f, eil[i]);
  end; { skaityti }

  function didz (ilg: integer; eil: eilute): integer;
    { i�renkamas did�iausias eilut�s elementas }
    var max, i: integer;
  begin
    max := eil[1];
    for i := 2 to ilg do
      if eil[i] > max
         then max := eil[i];
     didz := max;
  end; { did� }

  function max_2 (a, b: integer): integer;
  begin
    if a < b
       then max_2 := b
       else max_2 := a;
  end; { max_2 }

  function pagrindine (var f: text): integer;
    var n, { korio kra�tin�s ilgis }
        i, j, ilg, max, max2, max1, kair, des: integer;
        nau_nek, nau_dab, nau_suk, eil_suk, eil_nek, eil: eilute;
  begin
    readln (f, n); { korio kra�tin�s ilgis }
    { perskaitoma pirmoji eilut� }
    ilg := n; { pirmosios eilut�s ilgis }
    skaityti (f, ilg, eil);
    { randamas jos did�iausias elementas }
    max := didz (ilg, eil);
    eil_nek := eil;
    for i := 1 to n do
      eil_suk[i] := max;
    { skaitome po vien� korio eilut� ir ie�kome did�iausio kelio }
    for i := 2 to 2*n-1 do
      begin
        { perskai�iuojame eilut�s ilg� }
        if i <= n then ilg := ilg + 1
                 else ilg := ilg - 1;
        { skaitome tolesn� eilut� }
        skaityti (f, ilg, eil);
        { jei sukeitimas dar nebuvo atliktas arba atliktas �ioje eilut�je }
        max := didz (ilg, eil);
        for j := 1 to ilg do
          begin
            { kairioji �aka }
            if (j = 1) and (i <= n) then kair := -1
             else if i <= n then kair := eil_nek[j-1]
                            else kair := eil_nek[j];
            { de�inioji �aka }
            if (j = ilg) and (i <= n) then des := -1
             else if i <= n then des := eil_nek[j]
                            else des := eil_nek[j+1];
            nau_nek[j] := max_2(kair, des) + eil[j];
            nau_dab[j] := max_2(kair, des) + max;
          end;
        { jei sukeitimas atliktas ankstesn�se eilut�se }
        for j := 1 to ilg do
          begin
            { kairioji �aka }
            if (j = 1) and (i <= n) then kair := -1
             else if i <= n then kair := eil_suk[j-1]
                            else kair := eil_suk[j];
            { de�inioji �aka }
            if (j = ilg) and (i <= n) then des := -1
             else if i <= n then des := eil_suk[j]
                            else des := eil_suk[j+1];
            nau_suk[j] := max_2(kair, des) + eil[j];
          end;
        { atnaujinamos reik�m�s }
        eil_nek := nau_nek;
        for j := 1 to ilg do
          eil_suk[j] := max_2(nau_dab[j], nau_suk[j])
      end;
    { i�renkame did�iausi� reik�m� }
    max1 := didz (ilg, eil_suk);
    max2 := didz (ilg, eil_nek);
    pagrindine := max_2(max1, max2);
  end; { pagrindin� }

  procedure atidaryti_byla (var f: text);
  begin
    assign (f, PR);
    reset (f);
  end; { atidaryti_byl� }

  procedure uzdaryti_byla (var f: text);
  begin
    close (f);
  end; { u�daryti_byl� }

  procedure spausdinti (rez: integer);
    var f: text;
  begin
    assign (f, RZ);
    rewrite (f);
    writeln (f, rez);
    close (f);
  end; { spausdinti }

  var f: text;
      rez: integer;
begin
  atidaryti_byla (f);
  rez := pagrindine (f);
  uzdaryti_byla(f);
  spausdinti (rez);
end.