- Time limit: 1.00 s
- Memory limit: 512 MB
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].