afise

Campania electorală s-a terminat de mult, dar zidul din parcul central al orașului în care au fost puse afișele este încă într-o formă dezolantă. Ploile și vântul au acționat și au urâțit și mai mult această zonă pe care altă dată erau afișe frumos colorate. Primăria a decis să se ocupe de această problemă. A format o comisie și a decis realizarea unor panouri reclamă care să ascundă porțiunile deteriorate.

Deoarece fondurile sunt mici s-a decis să fie alocate doar un anumit număr de panouri publicitare care trebuie să ocupe o suprafață cât mai mică posibil. Comisia a primit datele din teren sub forma: lungime zid, câte unități sunt ocupate cu afișe ce trebuie acoperite și care este numărul de panouri pe care le poate folosi. De asemenea se primesc ca date și care sunt unitățile de zid ocupate cu afișe deja deteriorate.

Cerință

Fiind date lungimea zidului, câte unități sunt deteriorate, care este numărul maxim de panouri ce pot fi folosite și care sunt unitățile de zid deteriorate, se cere să se determine lungimea minimă totală a panourilor care sunt folosite pentru a acoperi zona și câte panouri se folosesc. Lungimea minimă o definim ca numărul total de unități de zid acoperite astfel încât să fie mascate zonele problemă. Pentru acoperirea unităților de zid deteriorate, nu este neapărat necesar să se folosească toate panourile. Numărul de panouri folosite fiind limitat există posibilitatea să fie acoperite și zone din zid care sunt curate.

Date de intrare

Fișierul de intrare afise.in conține pe prima linie $3$ valori separate prin câte un spațiu $L \ n \ k$, cu semnificația: $L$ lungimea totală a zidului, $n$ numărul de unități ce urmează a fi acoperite și $k$ numărul maxim de panouri ce pot fi folosite. Pe a doua linie separate prin câte un spațiu sunt $n$ valori $x_1, x_2, \dots, x_n$, unde xi reprezintă unitatea din zid care este acoperită de un afiș vechi. Valorile $x_1, x_2, \dots, x_n$, apar într-o ordine aleatoare.

Date de ieșire

Fișierul de ieșire afise.out conține o singură linie cu două valoari ce reprezintă lungimea minimă totală folosită și numărul de panouri folosite astfel încât toate zonele deteriorate să fie acoperite.

Restricții și precizări

• $0 < L \leq 1 \ 000$;
• $0 < n \leq L$;
• $0 < k \leq L / 2$;

Exemplul 1

afise.in

25 8 3
3 11 6 4 19 15 20 12

afise.out

11 3

Explicație

Zidul are lungimea egală cu $25$ de unități, iar $8$ dintre ele conțin afișe care trebuiesc acoperite cu maxim $3$ panouri. Se vor folosi toate cele $3$ panouri care vor totaliza $11$ unități, acoperind zonele $3-6$, $11-15$ și $19-20$.

Exemplul 2

afise.in

10 4 6
7 3 8 1

afise.out

4 3