Horgászat

John horgászni indul télvíz idején. Erre összesen H órányi ideje van (1<=H<=16), ezalatt L darab léket látogathat meg (2<=L<=25) a megadott sorrendben. Az 1. sorszámú léktől indul, s léktől lékig vándorol. Nem kell minden léknél megállnia, de nem szükséges minden lékhez eljutnia. Minden i=1, …, L-1 számhoz kapcsolunk egy t_i értéket, amely az i-edik és az (i+1)-ik lék közötti út bejárásához szükséges időt fejezi ki 5 perces időegységekben. (0<t_i<=192). Ha t₃=4, akkor a 3. és 4. lék közötti út 20 percbe telik.

Az út megtervezéséhez egyéb információink is vannak. Minden egyes léknél az első 5 percben várhatóan f_i darab hal akad horogra. (f_i>=0). Ezt követően minden 5 percben a fogható halak mennyisége d_i-vel csökken. (d_i>=0) Ha a fogható halak mennyisége eléri a d_i-t, vagy az alá csökken, akkor a következő 5 perces időszak végére egyetlen halunk sem marad.

Feladat:

Írj programot, amely segít megtervezni a horgásztúrát olyan módon, hogy John a lehető legtöbb halad fogja.

Bemenet:

A bemeneti állomány N darab tesztesetet tartalmaz. Minden eset a lékek számát tartalmazó sorral kezdődik. A következő sorban a rendelkezésre álló idő, azaz a H értéke szerepel. A következő sor az f_i, az azt követő a d_i értékeket foglalja magában, majd a harmadikban (L-1) szám, a t_i értékek szerepelnek.

Kimenet:

A kimeneti állományban minden tesztesetnél fel kell tüntetni az egyes lékeknél eltöltött időt vesszővel elválasztva. A következő sorba a kifogott halak számát kell bejegyezni.

Példa:

fish.in	fish.ans
3 2 1 10 1 2 5 2 4 4 10 15 20 17 0 3 4 3 1 2 3 4 4 10 15 50 30 0 3 4 3 1 2 3	45, 5 A kifogott halak száma: 31 240, 0, 0, 0 A kifogott halak száma: 480 115, 10, 50, 35 A kifogott halak száma: 724

(ACM ELTE csapatverseny 2000)