A2 - Veľký vlakový problém

Ak ste cestovali vlakom, určite ste si vo vozňoch všimli sprievodcov. Každý vlakový sprievodca má na starosti nejakú časť za sebou idúcich vozňov vlaku a jeho úlohou je starať sa o cestujúcich v týchto vozňoch. Vlaky železničnej spoločnosti Pavla Jozefa Šafárika sú povinne miestenkové a miestenky musia byť kúpené niekoľko hodín vopred. Sprievodcovia tak dopredu vedia, koľko ľudí bude cestovať v jednotlivých vozňoch a teda koľko ľudí budú musieť mať na starosti. Pred každou jazdou majú sprievodcovia veľkú dilemu. Ako si rozdeliť vozne vlaku (a tak aj cestujúcich) čo najspravodlivejšie - teda tak, aby sprievodca, ktorý bude mať na starosti najviac cestujúcich, ich mal čo najmenší možný počet.

Úloha

Vytvorte program, ktorý pre zadané obsadenie vozňov vlaku a počet sprievodcov vypočíta, aký maximálny počet cestujúcich bude mať na starosti jeden sprievodca pri najspravodlivejšom rozdelení, t.j. pri rozdelení, kedy tento maximálny počet bude najmenší možný. Zároveň pre každé rozdelenie sprievodcov musí platiť:

• každý sprievodca má na starosti nejakú časť za sebou zaradených vozňov vlaku (t.j. súvislú časť vlaku),
• každý sprievodca má na starosti aspoň jeden vozeň,
• o každý vozeň sa stará práve jeden sprievodca.

Vstup

Prvý riadok vstupu obsahuje počet vlakov M (1 ≤ M ≤ 100), pre ktoré treba nájsť vhodné rozdelenie vozňov vlaku jednotlivým sprievodcom. V každom z M ďalších riadkov sú údaje o jednom vlaku. Každý riadok začína dvomi medzerou oddelenými číslami K a N (1 ≤ K ≤ N). Číslo K určuje počet sprievodcov pridelených tomuto vlaku a číslo N počet vozňov vlaku. Za číslom N nasleduje N medzerami oddelných kladných čísel (≥ 1) menších ako 200 vyjadrujúcich počet cestujúcich v jednotlivých vozňoch.

Výstup

Výstup má obsahovať M riadkov, pričom i-ty riadok obsahuje maximálny počet cestujúcich, ktorých bude mať na starosti jeden sprievodca pri optimálnom rozdelení vozňov i-teho vlaku na vstupe.

A1

A2

Príklad

Vstup:

2
3 9 10 20 30 40 50 60 70 80 90
2 5 20 32 30 10 10 

Výstup:

170
52