drum

Fie P, de coordonate carteziene (a,b,c), şi Q, de coordonate carteziene (x,y,z), două puncte distincte din spaţiul tridimensional. Pe mulţimea punctelor din spaţiu se defineşte relaţia de ordine < astfel: un punct P este mai mic decât un punct Q (adică P<Q) dacă este satisfăcută una dintre relaţiile:

1. a<x;
2. a=x şi b<y;
3. a=x, b=y şi c<z.

Fie n un număr natural nenul şi M mulţimea ordonată crescător, pe baza relaţiei de ordine <, a tuturor punctelor din spaţiu ale căror coordonate (k,i,j) sunt numere naturale şi satisfac condiţiile: 1≤k≤n, 1≤i≤k, 1≤j≤k. Numărul punctelor din mulţimea M este $m=1+4+9+...+n^2$. Punctele din mulţimea ordonată M se numerotează cu numerele distincte 1,2,...,m în ordinea în care apar în aceasta.

Fiecărui punct din mulţimea ordonată M i se asociază câte o valoare naturală nenulă. Astfel, primului punct $P_1∈M$ i se asociază valoarea $c_1$, celui de-al doilea punct $P_2∈M$ se asociază valoarea $c_2$, ..., celui de-al m-lea punct $P_m∈M$ se asociază valoarea $c_m$, iar $P_1 < P_2 < ... < P_m$.

Pornind de la punctul $P_1$ de coordonate (1,1,1), se contruiesc drumuri astfel încât succesorul unui punct de pe drum, de coordonate carteziene (k,i,j), poate fi unul dintre cele 3 puncte din M ale căror coordonate sunt: (k+1,i,j+1), (k+1,i+1,j), (k+1,i+1,j+1), pentru 1≤k<n. De exemplu, dacă n>3 succesorul punctului de coordonate (3,1,2) poate fi oricare din punctele de coordonate: (4,1,3), (4,2,2), (4,2,3). Dacă n=3 atunci punctul de coordonate (3,1,2) nu are succesor.

Drumul $A_1,A_2,A_3,...,A_n$ precede lexicografic drumul $B_1,B_2,B_3,…,B_n$ dacă există un indice j (1≤j≤n) astfel încât $A_i=B_i$ (1≤i<j) şi $A_j < B_j$.

Cerinţă

Scrieţi un program care să citească numărul natural nenul n şi cele m numere naturale nenule $c_1, c_2, ..., c_m$ şi apoi să determine şi să afişeze suma maximă S care se poate obţine însumând toate valorile asociate punctelor de pe un drum construit în modul descris în enunţ, precum şi drumul pentru care se obţine suma maximă. Dacă există mai multe drumuri pentru care se obţine suma maximă, se va afişa primul drum din punct de vedere lexicografic.

Date de intrare

Fişierul de intrare drum.in conţine pe prima linie un număr natural nenul n. A doua linie conţine m numere naturale nenule $c_1,c_2,...,c_m$, separate prin câte un spaţiu, reprezentând valorile asociate punctelor din mulţimea ordonată M.

Date de ieşire

Fişierul de ieşire drum.out va conţine pe prima linie un număr natural reprezentând suma maximă S. A doua linie va conţine un drum pentru care se obţine suma maximă S, scriindu-se numărul fiecărui punct aflat pe drum, în ordinea parcurgerii acestora, numerele separându-se prin câte un singur spaţiu.

Restricţii şi precizări

• $1 ≤ n ≤ 30; 1 ≤ c_i < 100, 1 ≤ i ≤ m$
• Punctele de coordonate (n,i,j) nu au succesori (1≤i≤n, 1≤j≤n)
• Pentru suma maximă S corectă se acordă 60% din punctaj; pentru un drum pentru care se obţine suma maximă S se acordă 20% din punctaj, iar pentru primul drum din punct de vedere lexicografic pentru care se obţine suma maximă S se acordă 40% din punctaj.

Exemplu

drum.in

3
3 6 5 7 2 4 5 8 7 6 1 7 8 13

drum.out

18
1 4 13

Sunt 14 puncte în mulţimea M. Suma maximă care se poate obţine este 18, valoare ce se va scrie pe prima linie a fişierului drum.out. Sunt 2 drumuri pentru care se obţine suma maximă: $(P_1,P_4,P_{13})$ şi $(P_1,P_5,P_{14})$. Primul drum fiind cel mai mic (lexicografic) se vor scrie pe a doua linie a fişierului drum.out numere 1 4 13, obţinându-se punctajul maxim.