Problem C
Kaffi

Bóas er að smíða nýja háskólabyggingu og ætlar að hafa þar tiltekið herbergi til að geyma stóla. Þessa geymslu getur hann látið vera eins háa og honum lystir en hún þarf að vera $w$ metrar á breidd. Stólarnir sem hann ætlar að geyma í geymslunni eru allir eins, fyrir utan litinn. Þeir eru einn meter á breidd og hægt er að stafla þeim saman. Ef $k$ stólum er staflað hverjum ofan á annan verður staflinn $k$ metrar á hæð.

Bóas vill hafa skipulag á geymslunni, svo allir allir stólarnir í gefnum stafla þurfa að vera eins á litinn. Einnig komast bara fyrir $w$ staflar af stólum fyrir í geymslunni því geymslan er $w$ metrar breið. Bóas vill líka að geymslan sé snyrtileg. Bóas mælir ósnyrtileika sem flatarmál veggjarins bakvið stólana að fremri flatarmáli stólanna frádregnu. Getur þú hjálpað honum að finna minnsta ósnyrtileika sem hann getur náð ef hann staflar stólunum eftir reglunum að ofan?

Möguleg lausn á ‘sample input 1’. Ósnyrtileika stigið er þá summu flatarmála hvítu svæðana, $3 + 2 + 1 + 3 = 9$.

Inntak

Fyrri lína inntaksins inniheldur tvær tölur, $1 \leq n \leq 10^5$ og $n \leq w \leq 10^9$, þar sem $n$ táknar fjölda lita sem stólarnir hans Bóasar koma í og $w$ er breidd geymslunnar. Seinni lína inntaksins inniheldur $n$ heiltölur $1 \leq e_ i \leq 10^9$, þar sem $e_ i$ gefur til kynna fjölda stóla sem Bóas á af $i$-tta litnum.

Úttak

Eina lína úttaksins inniheldur minnsta ósnyrtileika sem Bóas getur náð.

5 23
21 14 24 7 17

9

5 23
13 19 19 30 1

10