Un primar are de acoperit un perete lung de W metri si inalt de 1 metru, pe care vrea sa il impanzeasca cu postere publicitare. In acest scop, are la dispozitie n postere, toate de inaltime egala cu 1 metru, avand latimile date.
Posterele trebuie asezate de-a lungul peretelui, fara sa se suprapuna si fara sa depaseasca marginile peretelui (fiecare poster poate fi folosit cel mult o data). Determinati aria maxima de perete (in m^2) care poate fi acoperita folosind o parte dintre posterele disponibile.
- Date de intrare
- Pe prima linie se citesc doua numere naturale W si n. Pe a doua linie se citesc n numere naturale, reprezentand latimile posterelor.
- Date de iesire
- Se afiseaza un singur numar natural, aria maxima acoperita.
- Restrictii
- 1 <= W <= 5000 1 <= n <= 50 1 <= latime poster <= W
Exemple
Exemplul 1
Intrare
100 8 12 27 13 25 26 38 28 38
Iesire
94
Exemplul 2
Intrare
10 3 3 4 5
Iesire
9