Doi prieteni au inventat un nou joc — jocul pietricelelor. Ei au la dispoziţie grămezi, fiecare dintre ele conţinând un număr distinct de pietricele. Jocul constă în alegerea unui număr oarecare de grămezi din cele date, pentru a obţine în total (adunând numărul de pietricele din grămezile selectate) un număr de pietricele cu mai mare decât ultimul număr obţinut de partenerul de joc. Primul jucător trebuie să obţină la prima sa mutare un total de pietricică. Deci, obligatoriu al doilea jucător trebuie să obţină la prima sa mutare un total de pietricele. La a doua mutare, primul jucator este obligat sa obţină un total de pietricele, ş.a.m.d. Câştigă cel care a obţinut totalul maxim, sau, altfel spus, pierde cel care nu reuşeşte să obţină la rândul său un total cu exact o pietricica mai mare decât ultimul total obţinut de partenerul de joc.
Cerință
Scrieţi un program care determină numărul de pietricele obţinut la ultima sa mutare de jucătorul câştigător.
Date de intrare
Fişierul de intrare joc.in conţine:
- pe prima linie numărul de grămezi;
- pe a doua linie numere ordonate crescător, reprezentând numărul de pietricele din fiecare grămadă (vectorul ).
Date de ieșire
Fişierul de ieşire joc.out va conţine pe prima linie numărul determinat.
Restricții și precizări
- .
- Pentru teste în valoare de de puncte, , iar toate numerele care intervin în problemă sunt mai mici decât .
- Valorile din vectorul sunt ;
- Testele și restricțiile au fost refăcute pentru a face problema conformă cu nivelul la care s-a dat și cu anul .
Exemplu
joc.in
7
1 2 4 9 10 11 12
joc.out
7
Explicație
Notam primul jucător şi al doilea jucător.
are la dispoziţie o grămadă cu o pietricică:
are la dispoziţie o grămadă ce conţine două pietricele:
alege primele două grămezi:
are la dispoziţie o grămadă ce conţine 4 pietricele:
alege prima şi a trei grămadă:
alege a doua şi a treia grămadă:
alege primele trei grămezi:
Jocul ia sfârşit deoarece al doilea jucător nu poate obţine o grămadă ce conţine pietricele.