Lemmings

Lemmings este un joc video de strategie extrem de popular în anii 1990. Lemingii sunt niște rozătoare mici (șoricei), care viețuiesc mai ales în tundra din jurul Cercului Arctic. Sunt erbivori, hrănindu-se mai ales cu bulbi și rădăcini. Vizuinile lor au camere de odihnă, de hrană și camere de joacă.

Avem $N$ camere numerotate de la $1$ la $N$, dispuse circular. $M$ camere conțin hrană, iar $K$ lemingi sunt poziționați în camerele lor de odihnă care nu conțin hrană.

Dacă un leming se află în camera $i$ și se deplasează spre dreapta, ajunge în camera $i + 1$ (cu circularitate: dacă este în camera $N$, merge în camera $1$). Dacă se mișcă spre stânga, ajunge în camera $i − 1$ (cu circularitate: dacă este în camera $1$, merge în camera $N$).

Trecerea dintr-o cameră în alta se face într-o unitate de timp.

Fiecare leming alege o direcție fixă de deplasare (stânga sau dreapta), și va merge constant în această direcție pentru următoarele $T$ unități de timp. Lemingii nu staționează.

Dacă un leming se află într-o cameră cu hrană, el consumă instantaneu hrana respectivă și își continuă deplasarea.

Dacă doi lemingi se intersectează (se întâlnesc) aceștia dispar. Dacă se întâlnesc într-o cameră în care este hrană, unul dintre ei consumă hrana înainte de a dispărea.

Cerință

Să se determine cantitatea maximă de hrană consumată de șoricei în $T$ unități de timp.

Date de intrare

Fișierul de intrare lemmings.in conține pe prima linie numerele naturale $N$ $M$ $K$ $T$, cu semnificația din enunț. Pe următoarea linie numerele celor $M$ camere care conțin hrană, în ordine strict crescătoare. Ultima linie din fișier conține numerele celor $K$ camere unde se află inițial lemingii, de asemenea în ordine strict crescătoare.

Date de ieșire

Fișierul de ieșire lemmings.out conține o singură linie pe care este scris un număr ce reprezintă cantitatea maximă de hrană consumată de lemingi.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• $1 \leq M, K \leq 20 \ 000$
• $1 \leq T \leq 500$

Exemplul 1

lemmings.in

11 4 5 2
2 4 5 11
1 3 7 9 10

lemmings.out

4

Explicație

În primul exemplu, avem $N = 11$ camere din care $M = 4$ conțin hrană (camerele $2$ $4$ $5$ $11$). Cei $K = 5$ lemingi se află în camerele $1$ $3$ $7$ $9$ $10$. După $T = 2$ unități de timp cantitatea maximă de hrană consumată este egală cu $4$. O soluție posibilă este ca toți lemingii să meargă spre dreapta.

Exemplul 2

lemmings.in

13 6 4 2
1 3 7 8 9 13
2 6 10 11

lemmings.out

5

Explicație

În al doilea exemplu, o posibilă alegere a direcțiilor este:

• Lemingul aflat în camera $2$ merge spre stânga.
• Lemingul aflat în camera $6$ merge spre dreapta.
• Lemingul aflat în camera $10$ merge spre stânga.
• Lemingul aflat în camera $11$ merge spre dreapta.