Se dau n valize, cu capacitatile c_1, c_2, ..., c_n litri. Pentru o submultime de valize alese, calculam suma capacitatilor acestora (submultimea vida are suma 0).
Determinati suma maxima s astfel incat sa existe exact doua submultimi distincte de valize a caror suma a capacitatilor sa fie egala cu s. Daca nu exista nicio astfel de suma, afisati -1.
- Date de intrare
- Pe prima linie se citeste numarul intreg n. Pe a doua linie se citesc n numere intregi, capacitatile valizelor.
- Date de iesire
- Se afiseaza un singur numar intreg: suma maxima obtinuta in exact doua moduri, sau -1 daca nu exista.
- Restrictii
- 3 <= n <= 18 1 <= c_i <= 500
Exemple
Exemplul 1
Intrare
6 14 3 16 8 2 5
Iesire
43
Exemplul 2
Intrare
3 1 1 1
Iesire
-1