Uolevilla on merkkijono joka on n merkkiä pitkä. Uolevi haluaa katkaista merkkijonon m eri kohdasta, jolloin merkkijono katkeaa m+1 eri osaan. Osien pituudet järjestyksessä vasemmalta oikealle ovat a_1, \ldots, a_{m+1}. Kun Uolevi katkaisee x merkkiä pitkän merkkijonon, hän käyttää x operaatiota. Mikä on pienin määrä operaatiota joilla Uolevi saa hajotettua merkkijonon?

Syöte

Syötteen ensimmäisellä rivillä on kaksi lukua, n ja m, merkkijonon pituus ja monestako kohdasta merkkijono pitää katkaista. Seuraavalla m+1 rivillä on luvut, a_1, \ldots, a_{m+1}, merkkijonon osien pituudet katkaisujen jälkeen.

Tuloste

Tulosta yksi luku, pienin määrä operaatiota merkkijonon hajottamiseen.

Rajat

• 1 \le n \le 10^9
• 1 \le m \le 400
• 1 \le a_i
• \sum_{i=1}^{m+1}{a_i} = n

Esimerkki

Syöte:

8 2
3
3
2

Tuloste:

13

Uolevi katkaisee 8 merkkiä pitkän merkkijonon ensin osiin joiden pituudet ovat 3 ja 5. Sen jälkeen Uolevi katkaisee 5 merkkiä pitkän osan osiin joiden pituudet ovat 3 ja 2.

Syöte:

20 4
2
1
5
2
10

Tuloste:

40