DMIH 1996., Supetar, 15. - 19. travnja
2. Hrvatska informatička olimpijada
2. zadatak - Ugljen
80 bodova

Radno vrijeme jednog mini-rudnika počinje u 8 sati ujutro. Neki patuljci-rudari koji rade u tom rudniku su jači, a neki slabiji tj. neki brže iskapaju ugljen i tovare ga u prašnjave vagončiće, a neki to rade sporije. Od tog napornog rada oni se umaraju i ne mogu raditi predugo bez da malo izađu iz rudnika odmoriti se na svjež zrak. Patuljci mogu ulaziti i izlaziti iz rudnika samo na svaki puni sat. Kad patuljak izađe iz rudnika, on mora ostati izvan rudnika određeni broj sati. Zbog teških uvjeta rada u rudniku, patuljci na pauzi redovito piju Red Bull koji im pomaže da nakon odmora nastave raditi kao da tog dana ranije nisu ni primirisali rudniku. Također, neki su patuljci međusobno posvađani i ni pod koju cijenu ne žele raditi istovremeno u rudniku (to ih ne sprječava da se istovremeno odmaraju, jer je livada ispred rudnika jako velika i zavađeni patuljci će se moći držati podalje jedni od drugih, dok u rudniku zbog skučenosti prostora to nije moguće).
Treba napraviti program koji će na temelju pročitanih ulaznih podataka izračunati maksimalnu moguću količinu iskopanog ugljena u toku radnog vremena.

ULAZNI PODACI

Program učitava podatke iz tekstualne datoteke UGLJEN.IN u kojoj se podaci nalaze zapisani u slijedećem obliku :

n
s
a1 a2 ... an
b1 b2 ... bn
p
m1,1
m2,1 m2,2
  ...
mn,1 mn,2 ... mn,n


Objašnjenja uz oznake :

n ... broj patuljaka zaposlenih u rudniku (2(n(5)
s ... duljina radnog vremena rudnika u satima (1(s(8)
ai ... maksimalni broj sati koliko i-ti patuljak može raditi bez odmora (1(ai(8) (dok ukupno vrijeme koje patuljak može provesti u rudniku nije ograničeno)
bi ... količina ugljena (u tonama) koliko i-ti patuljak iskopa za sat vremena (1(bi(5)
p ... duljina pauze (minimalan broj sati koji patuljak mora ostati izvan rudnika kad izađe) (1(p(4)
mi,j ... ukoliko je ova vrijednost jednaka 1 onda se i-ti i j-ti patuljak ne podnose i ne mogu raditi istovremeno u rudniku (ako se ipak vole, na ovom mjestu piše 0). Kako svaki patuljak voli samog sebe, podrazumijevamo da je   mi,i = 0 za 1(i(n.

Svi brojevi koji se učitavaju iz ulazne datoteke su nenegativni cijeli brojevi.

IZLAZNI PODACI

Program treba u tekstualnu datoteku UGLJEN.OUT ispisati samo količinu iskopanog ugljena (u tonama) za onaj raspored rada patuljaka kod kojeg će ta količina biti maksimalna (naravno, taj raspored rada patuljaka mora zadovoljavati sve gore navedene uvjete iz zadatka).

PRIMJERI

1.)

UGLJEN.IN

2
4
1 2
3 5
1
0
0 0

UGLJEN.OUT

21

2.)

UGLJEN.IN

4
8
1 2 3 4
2 3 4 5
2
0
1 0
0 1 0
0 1 1 0

UGLJEN.OUT

44

NAPOMENA

Rješenje zadatka snimiti na disk (u direktorij C:(DMIH(HIO) i na disketu (direktorij A:() pod imenom UGLJEN.C (odnosno UGLJEN.PAS ili UGLJEN.BAS). Ukoliko je zadatak riješen u Pascal-u ili C-u, potrebno je u te iste direktorije spremiti izvršnu verziju programa (UGLJEN.EXE).

Program mora generirati rješenje unutar 10 sekundi.