Snímkování zákrytů

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

     

Obrázek 1. Schémata a), b), c) odpovídají řešením příkladů 1, 2, 3, níže. První řádek představuje časovou osu, druhý řádek představuje posloupnost časů jednotlivých zákrytů, třetí řádek představuje posloupnost snímkovacích cyklů s vyznačenými časy uvnitř cyklů, v nichž lze snímkovat.

Ú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 ≤ t₁ < t₂ < ... < t_N ≤ 10⁷, 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 ≤ c₁ < c₂ < ... < c _L < L ≤ 10⁵, 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 ≤ 10⁴, 1 ≤ M ≤ 10³.

Výstup

Výstup obsahuje jeden textový řádek s celým číslem udávajícím maximální možný počet snímkovaných zákrytů.

Příklad 1

Vstup

10
1 2 4 5 8 9 12 13 15 16
2 4
1 2

Výstup

8

Příklad 2

Vstup

13
1 3 5 6 7 11 13 14 18 20 21 22 26
4 7
0 1 2 6 

Výstup

12

Příklad 3

Vstup

11
10 12 14 16 18 20 22 24 26 28 30
3 8
0 2 4 

Výstup

9

---

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