Strop

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 rady 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.

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 prvé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 řádku, 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á 50cm a 1 prkno dlouhé 100cm.

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říklad 1

Vstup:

100 20
10
3
2 1 1 100
3 1 1 100
4 1 5 50

Výstup:

2

Příklad 2

Vstup:

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

Výstup:

0

Příklad 3

Vstup:

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

Výstup:

33

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:

6866

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