- Time limit: 4.00 s
- Memory limit: 128 MB
Sinulle on annettu tiedot asuntojen hakijoista ja vapaana olevista asunnoista, ja tehtäväsi on jakaa asunnot niin, että mahdollisimman moni hakija saa asunnon.
Jokaisella hakijalla on toive asunnon koosta, ja hakija hyväksyy minkä tahansa asunnon, jonka koko on riittävän lähellä toivetta.
Syöte
Syötteen ensimmäisellä rivillä on kolme kokonaislukua n, m ja k: hakijoiden määrä, asuntojen määrä ja suurin sallittu poikkeama.
Seuraavalla rivillä on n kokonaislukua a_1, a_2, \ldots, a_n: jokaisen hakijan toive asunnon koosta.
Jos hakijan toive on x, hän hyväksyy minkä tahansa asunnon, jonka koko on vähintään x-k ja korkeintaan x+k.
Viimeisellä rivillä on m kokonaislukua b_1, b_2, \ldots, b_m: jokaisen asunnon koko.
Tuloste
Ohjelmasi täytyy tulostaa yksi kokonaisluku: moniko hakija saa asunnon.
Rajat
- 1 \le n \le 10^5
- 1 \le m \le 10^5
- 0 \le k \le 10^9
- 1 \le a_i \le 10^9
- 1 \le b_i \le 10^9
Esimerkki
Syöte:
4 3 5 60 45 80 60 30 60 75
Tuloste:
2