Sinulla on lauta, jonka pituus on $x$. Haluat jakaa sen $n$ laudaksi, joiden pituudet ovat $p_1,p_2,\ldots,p_n$.

Jokaisella vuorolla voit valita minkä tahansa laudan ja jakaa sen kahteen osaan haluamallasi tavalla. Tällaisen jaon kustannus on laudan pituus ennen jakoa.

Mikä on pienin mahdollinen kaikkien kustannusten summa?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $x$ ja $n$: alkuperäisen laudan pituus ja haluttujen lautojen määrä.

Seuraavalla rivillä on $n$ kokonaislukua $p_1,p_2,\ldots,p_n$: halutut pituudet.

Tuloste

Tulosta yksi kokonaisluku: pienin kokonaiskustannus.

Rajat

• $1 \le x \le 10^9$
• $1 \le n \le 5 \cdot 10^5$
• $p_i >= 1$
• $p_1+p_2+\ldots+p_n=x$

Esimerkki

Syöte:

8 3
2 3 3

Tuloste:

13

Selitys: Alussa laudat ovat $[8]$. Jaat $8$:n pituisen laudan osiin $3+5=8$ (kustannus $8$), minkä jälkeen laudat ovat $[3,5]$. Sitten jaat $5$:n pituisen laudan osiin $2+3=5$ (kustannus $5$), minkä jälkeen laudat ovat $[2,3,3]$.