Snímkování zákrytů
Zadání
Quido po dlouhém experimentování sestavil družici, která bude snímkovat zákryty měsíců obřích planet. Měsíců je mnoho, jsou na různých nestabilních drahách a také družice bude měnit svou polohu, takže zákryty z pohledu družice budou nastávat nepravidelně. Hugo však dokázal dopředu propočítat přesně časy všech zákrytů a tyto časy jsou tedy známy.
Družice je nízkonákladová a má některá omezení. Nemůže snímkovat kdykoli. Snímkování může probíhat pouze v tzv. cyklech.
Družice může provést libovolný počet cyklů, ale nemůže začít další cyklus předtím, než doběhne předchozí cyklus. Další cyklus může následovat buď okamžitě po skončení předchozího cyklu nebo lze před zahájením dalšího cyklu libovolně dlouhou dobu počkat. V jednom cyklu lze snímkovat pouze ve fixně určených okamžicích po zahájení cyklu, takže průběh každého cyklu je zcela identický.
Quido chce nasnímkovat co největší počet zákrytů.
Úloha
Jsou dány časy jednotlivých zákrytů a možné časy snímkování během jednoho cyklu družice. Určete maximální možný počet snímkovaných zákrytů.
Vstup
První řádek obsahuje jedno celé číslo N představující celkový počet zákrytů, které lze snímkovat. Na druhém řádku je uvedena celočíselná posloupnost 0 ≤ t1 < t2 < … < tN ≤ 107, představující okamžiky, v nichž jednotlivé zákryty nastanou. Sousední členy posloupnosti jsou odděleny mezerou. Na třetím řádku jsou uvedena dvě celá čísla M a L oddělená mezerou. M představuje počet časových okamžiků během jednoho cyklu družice, v nichž lze snímkovat. L představuje dobu trvání jednoho cyklu. Na čtvrtém řádku je uvedena celočíselná celočíselná posloupnost 0 ≤ c1 < c2 < … < cL < L ≤ 105, představující okamžiky po začátku cyklu, v nichž lze během jednoho cyklu snímkovat.
Všechny časové údaje jsou uvedeny ve stejných jednotkách (lze si např. pro názornost představovat, že jsou to minuty).
Platí: 1 ≤ N ≤ 104, 1 ≤ M ≤ 103.