Strop

Zadání

Paní Marie z Písku v jižních Čechách si přeje realizovat architektonicky zajímavý strop v obývacím pokoji. Na zahradě má svazek prken různých délek a s různou tloušťkou, ale se stejnou šířkou. Práci s pilou považuje paní Marie za nebezpečnou, proto se žádné prkno nebude jakýmkoliv způsobem přiřezávat či zkracovat.

Hezký strop by proto mohl být pobit prkny následovně: Z prken se budou tvořit řady začínající na jedné straně stropu (na šířce stropu). Postupně se řadami pokryje druhá strana stropu (délka).

Žádné prkno dané tloušťky nesmí sousedit s prknem stejné tloušťky, ať už v dané řadě, či v sousedních řadách. Prkna stejné tloušťky se tedy smí dotýkat nejvýše rohy, ale jinak nesmí mít společnou hranu, protože by tím nebylo dosaženo žádaného strukturního vjemu.

Svazek prken je popsán vždy tloušťkou, délkou a počtem prken s danou tloušťkou a délkou. Strop je obdélník s určenou šířkou a délkou. Kresba dřeva nehraje při návrhu roli. Proto se varianty pokrytí stropu považují za různé, pokud existuje místo na stropu, které v jednotlivých variantách překrývá prkno jiné tloušťky nebo jiné délky.

Úkol

Kolik různých variant stropu může být vytvořeno z daného svazku prken?

Vstup

Vstupní soubor specifikuje nejprve rozměry obdélníkového stropu. Na prvním řádku jsou uvedena dvě celá kladná čísla oddělena jednou mezerou. Nejprve je uvedeno celé číslo udávající délku stropu, druhé číslo udává šířku stropu. Je zaručeno, že šířka stropu je násobek jednotné šířky prken.

Na druhém řádku je uvedena jednotná šířka všech prken představovaná kladným celým číslem.

Na třetím řádku je uveden počet různých tlouštěk prken, opět představovaný jedním kladným celým číslem.

Dále následuje ten samý počet řádků, z nichž každý určuje počty prken pro určitou délku a danou tloušťku prkna. Všechna čísla jsou celá a kladná a oddělena jednou mezerou. Nejprve je na každém řádku uvedena tloušťka, poté počet různých délek, pak následují dvojice čísel určující postupně počet prken a jejich délku.

Např. řádek

3 2 2 50 1 100 určuje prkna tloušťky 3 cm ve 2 délkách. Jsou tu 2 prkna dlouhá 50 cm a 1 prkno dlouhé 100 cm.

Výstup

Na výstupu bude uveden jeden řádek s jediným číslem, které bude vyjadřovat počet nalezených různých variant pokrytí stropu.

Pokud strop nelze pokrýt danými prkny podle požadavků, bude výstupní řádek obsahovat pouze číslo 0.

Příklady

Příklad 1

Vstup

Výstup

Příklad 2

Vstup

200 40
20
2
3 2 5 115 4 40
4 2 3 120 2 35

Výstup

Příklad 3

Vstup

300 10
10
3
2 1 1 100
3 2 2 50 1 100
4 1 2 50

Výstup

Příklad 4

Vstup

250 60
10
3
2 3 10 100 20 150 5 300
3 3 10 250 15 150 10 100
4 3 10 250 25 200 20 50

Výstup

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data