Sama tehtävä kuin Merkkijono, mutta syötteen koko on suurempi.

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 5000$
• $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