Time limit: 0.5s
Memory limit: 128MB
Input: stdin
Output: stdout
Anul acesta XB s-a decis să devină microbist și în sfârșit a început și el să se uite la Liga 1 (i se zice SuperLiga, dar cu toții știm cât de super e de fapt). Astfel, ca să se poată bucura de cât mai multe succese, XB a decis să se familiarizeze cu cum funcționează forma unor echipe și și-a creat propriul campionat cu echipe și etape, știind pentru fiecare echipă câte puncte obține în fiecare etapă , și anume .
Totuși, omul nostru este suporter de rezultat și, deși în fotbal loialitatea ar trebui să însemne mai mult, el nu concepe să rămână alături de aceeași echipă chiar și la greu, astfel că el își poate schimba echipa favorită de cel mult ori într-un sezon (el înțelege loialitatea oarecum, pur și simplu nu în totalitate).
Cerință
Astfel, scopul lui este să se poată bucura de cât mai multe puncte obținute de echipele lui favorite de-a lungul sezonului, știind că el poate să-și schimbe echipa favorită de cel mult ori. Dacă într-o etapă el ține cu echipa , punctajul de care se bucură va crește cu . Aflați acest scor maxim pentru el.
Date de intrare
Pe prima linie se găsesc trei numere naturale, , și , reprezentând numărul de echipe, numărul de etape și numărul maxim de schimbări de echipă favorită.
Pe următoarele linii se află câte numere naturale, reprezentând scorul obținut de echipa în etapa .
Date de ieșire
Pe prima linie se va găsi un singur număr, scorul maxim pe care îl poate obține XB dacă susține echipele potrivite.
Restricții și precizări
- ;
- ;
# | Punctaj | Restricții |
---|---|---|
0 | 0 | Exemplul |
1 | 9 | |
2 | 14 | |
3 | 44 | |
4 | 33 | Fără restricții suplimentare |
Exemplu
stdin
4 5 1
3 2 4 5 1
1 1 5 5 5
2 4 1 2 3
4 5 2 1 3
stdout
24
Explicație
XB poate ține mai întâi cu echipa timp de două etape, iar mai apoi va ține cu echipa , obținând astfel de puncte.