Favágás

Egy farönköt kell feldarabolnod. A legmegfizethetőbb cég (az Analog Cutting Machinery) a felvágandó rönkök hossza alapján számolja fel a díjat. A munkafolyamatuk miatt egyszerre csak egy vágást tudnak végrehajtani.

Könnyű észrevenni, hogy a vágások sorrendjének különböző megválasztása különböző árakat eredményezhet. Vegyünk például egy 10 méteres farönköt, amelyet az egyik végétől mérve 2, 4 és 7 méternél kell feldarabolnunk. Többféle lehetőségünk van. Vághatunk először 2, majd 4, végül 7 méternél. Ezzel az ár 10 + 8 + 6 = 24 lesz, mert az első vágást 10 méteres rönkön kell végrehajtani, a másodikat 8 méteresen, az utolsót pedig 6 méteresen. Egy másik lehetőség, hogy először 4 méternél vágunk, aztán 2-nél, végül 7-nél. Így az ár 10 + 4 + 6 = 20 lesz, amely jobb az előzőnél.

A főnököd megbízik a programozói tudásodban, és megkér, hogy számítsd ki egy adott farönk feldarabolásának a minimális költségét.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset első sorában egy l pozitív egész szám szerepel, amely a feldarabolandó farönk hosszát adja meg. Feltételezheted, hogy l < 1000. A következő sor n-et, a vágások számát tartalmazza (n < 50).

A következő sorban n pozitív egész szám (c_i) szerepel (0 < c_i < l), amelyek a vágási pontokat adják meg, szigorúan növekvő sorrendben.

A bemenet végét egy olyan teszteset jelzi, ahol l = 0.

A kimenet specifikációja

Minden tesztesetre a kimenetre kell írnod a vágási probléma optimális megoldásának költségét, azaz az adott farönk feldarabolásának minimális költségét. A kimenetet a példa kimenetben látható módon kell megformázni.

Példa bemenet

1. 100
2. 3
3. 25 50 75
4. 10
5. 4
6. 4 5 7 8
7. 0

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. The minimum cutting is 200.
2. The minimum cutting is 22.

letöltés szöveges állományként