Ministerstvá vnútra a dopravy sa rozhodli zvýšiť príjem štátnej pokladnice automatickým meraním rýchlosti na hlavnej diaľnici Košice-Bratislava a následným výberom pokút udelených za jej prekročnie. Dali si vypracovať štúdiu, koľko by stáli radary na jednotlivých miestach (na každom kilometri diaľnice). Boli prekvapení, aké rôzne ceny môžu byť v závislosti od umiestnenia radaru.
Namontovať ich každý jeden kilometer by bolo veľmi nákladné, tak vymysleli že budú kontrolovať úseky každých 10 km. Už chceli spisovať zmluvu so spriaznenou firmou, keď zrazu dostali ponuku oveľa lacnejšiu. Tá nebudovala radary presne každých 10 km, ale čo najlacnejšie tak, aby na ľubovoľnom 10 km úseku bol aspoň jeden radar. Teda, na ľubovoľnom súvislom 10 km úseky medzi dvoma kilometrovníkmi sa musí nachádzať aspoň jeden radar (je jedno či na jeho začiatku, konci, alebo niekde uprostred). Radary sú umiestnované vždy v celých násobkoch likometrov od začiatku diaľnice v Bratislave (teda používajú ceny zistené spomínanou štúdiou).
Úloha
Vytvorte program, ktorý pre zadané ceny a dĺžku úseku nájde optimálne (t.j. najlacnejšie) riešenie.
Vstup
Prvý riadok vstupu obsahuje jedno číslo, počet testovacích sád T.
Pre každú testovaciu sadu nasledujú dva riadky. Prvý riadok obsahuje dve celé čísla - celkovú dĺžku diaľnice N a dĺžku úseku, na ktorom musí byť kontrolovaná rýchlosť radarom K (1 ≤ k ≤ N ≤ 1.000)
Druhý riadok obsahuje N medzerou odelených celých čísel, cenu C osadenia radaru na danom kilometri.
Výstup
Výstupom je T riadkov, každý obsahujúci cenu najlacnejšieho osadenia radarov pri splnení podmienok pre príslušnú testovaciu sadu.
Príklad
Vstup:
2
3 2
2 1 2
4 3
1 5 5 1
Výstup:
1
2
Poznámka
V druhom prípade je lacnejšie postaviť dva radary namiesto jedného.
|