Šeštadieninė informatikos olimpiadininkų mokykla

Tomas nemėgsta skalbti drabužių, nors ir turi skalbimo mašiną. Kartais, kai Tomas nusprendžia išskalbti drabužius, jų jis turi tiek daug, kad jie visi netelpa į mašiną, ir jam tenka skalbti kelis kartus iš eilės.

Taip pat, Tomas žino, kad kartu skalbimo mašinoje galima skalbti tik tam tikrų spalvų drabužius. Tuomet sakome, kad drabužių spalvos priklauso vienai drabužių grupei. Kiekviena spalva priklauso lygiai vienai drabužių grupei.

Užduotis

Skalbimo mašinoje vienu metu negalima skalbti daugiau nei drabužių. Žinodami, kurių spalvų drabužius galima skalbti kartu, padėkite Tomui suskaičiuoti, kiek skalbimų jis turės atlikti, kad išskalbtų visus drabužius.

Pradiniai duomenys

Pirmoje eilutėje pateikti trys sveikieji skaičiai: – drabužių spalvų kiekis, – skirtingų drabužių grupių skaičius ir – skalbimo mašinos talpa.

Tolesnėse eilučių pateiktas sveikasis skaičius , nurodantis kiek skirtingų drabužių spalvų yra -toje grupėje ir dar skaičių – nurodančių kurios drabužių spalvos priklauso -taigrupei.

Kitoje eilutėje pateikta sveikųjų skaičių , nurodančių kiek -tosios spalvos drabužių Tomas turi.

Drabužių spalvos žymimos sveikaisiais skaičiais nuo 1 iki .

Rezultatai

Išveskite vieną sveikajį skaičių – skalbimų, kuriuos turės Tomas atlikti, skaičių.

Pavyzdžiai

7 3 3
3 1 2 6
1 4
3 3 5 7
3 3 0 2 4 1 2

6

Pirmosios grupės drabužius, kurių yra 7, galėsime išskalbti per 3 skalbimus, antrosios, kurių yra 2 – per 1, ir trečiosios, kurių yra 6 – per 2. Iš viso Tomui teks atlikti  skalbimus.

7 4 5
2 1 7
2 2 6
2 3 5
1 4
1 2 4 5 4 7 8

7

Pirmosios 3 grupės reikalaus atlikti po 2 skalbimus, o paskutinę grupę Tomas galės išskalbti vienu skalbimu. Iš viso reikės atlikti 7 skalbimus.

Ribojimai