echitabil

Dan şi George, buni prieteni, vor să plece pe munte cu cortul. Fiecare face cumpărături, adună bagajele apoi se întâlnesc la Dan şi se hotărăsc să împartă cât mai echitabil greutăţile între ei. Ca să nu existe suspiciuni, fac o listă cu toate obiectele pe care trebuie să le ia, le cântăresc apoi decid că distribuţia cea mai eficientă nu poate fi realizată decât cu ajutorul calculatorului (doar n-au absolvit profilul informatică degeaba).

Cerință

Cunoscând numărul de obiecte şi greutăţile acestora, să se determine o modalitate de repartizare a obiectelor astfel încât între greutăţile totale pe care le vor transporta cei doi prieteni diferenţa să fie minimă.

Date de intrare

Fişierul text echitabil.in are următoarea structură:

• $N$
• $g_1 \ g_2 \dots g_N$
  unde $N$ reprezintă numărul de obiecte, iar $g_1 \ g_2 \dots g_N$ greutăţile celor $N$ obiecte

Date de ieșire

Fişierul text echitabil.out are următoarea structură:

• $S_1 \ S_2$, reprezentand greutăţile totale rezultate prin împărţire $(S_1 \leq S_2)$
• $m$, reprezentand numărul de obiecte pe care le va transporta Dan
• $g_{i_1} \ g_{i_2} \dots g_{i_m}$, reprezentand greutăţile obiectelor pe care le va transporta Dan
• $p$, reprezentand numărul de obiecte pe care le va transporta George
• $g_{j_1} \ g_{j_2} \dots g_{j_p}$, reprezentand greutăţile obiectelor pe care le va transporta George

Restricții și precizări

• $2 \leq N \leq 1000$, număr natural
• $1 \leq g_i \leq 50, i = 1,2, \dots N$, numere naturale
• $m + p \leq N$
• Obiectele nu pot fi tăiate.
• Dacă există mai multe soluţii se va afişa una singură.

Exemplu

echitabil.in

6
4 7 7 17 29 49

echitabil.out

56 57
2
7 49
4
4 7 17 29