Se citesc lungimea L a unui baton si n pozitii la care trebuie facute taieturi (numere intre 0 si L). Fiecare taietura are un cost egal cu lungimea bucatii curente de baton pe care se face. Determinati, folosind Programarea Dinamica, costul minim total pentru a efectua toate cele n taieturi, alegand optim ordinea in care se fac.
- Date de intrare
- Pe prima linie se citesc L si n. Pe a doua linie se citesc cele n pozitii de taiere.
- Date de iesire
- Se afiseaza un singur numar: costul minim total al taieturilor.
- Restrictii
- 1 <= L <= 10^6, 0 <= n <= 100, 1 <= pozitie de taiere <= L-1
Exemple
Exemplul 1
Intrare
7 4 1 3 4 5
Iesire
16
Exemplul 2
Intrare
9 3 2 4 7
Iesire
18