Problem description


Kajaki
(oi04-kajaki)
Memory limit: 8 MB
Time limit: 1.00 s

Organizując spływ, wypożyczamy na przystani kajaki. Wszystkie kajaki są jednakowe. W jednym kajaku mogą popłynąć co najwyżej dwie osoby, a suma ich wag nie może przekroczyć ustalonego maksymalnego obciążenia. Aby zapłacić jak najmniej, szukamy sposobu rozmieszczenia wszystkich uczestników spływu w minimalnej liczbie kajaków.

Napisz program, który: - wczytuje maksymalne obciążenie kajaka, liczbę uczestników spływu i wagę każdego z nich, - oblicza minimalną liczbę kajaków, jakie należy wynająć, aby rozmieścić w nich wszystkich uczestników spływu w zgodzie z przepisami.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita w. Jest to maksymalne obciążenie kajaka. W drugim wierszu wejścia znajduje się jedna liczba całkowita n. Jest to liczba uczestników spływu. Następnie podane jest n wierszy. W i + 2 wierszu wejścia znajduje się jedna liczba naturalna wi oznaczająca wagę i-tego uczestnika spływu.

Wyjście

W pierwszym wierszu wyjścia należy wypisać jedną liczbę całkowitą - minimalną liczbę kajaków, jakie trzeba wynająć.

Ograniczenia

80 ≤ w ≤ 200, 1 ≤ n ≤ 30 000, 5 ≤ wi ≤ w

Przykład

Input Output
100
9
90
20
20
30
50
60
70
80
90
6