CSES 1084 ↗

Apartments

Maximum number of applicants that can be matched to distinct apartments whose size is within `k` of the applicant's wish.

18
submissions
0.973
best score

There are n applicants and m free apartments. Your task is to distribute the apartments so that as many applicants as possible will get an apartment.

Each applicant has a desired apartment size, and they will accept any apartment whose size is close enough to the desired size.

Input

The first input line has three integers n, m, and k: the number of applicants, the number of apartments, and the maximum allowed difference.

The next line contains n integers a1,a2,…,an: the desired apartment size of each applicant. If the desired size of an applicant is x, they will accept any apartment whose size is between x−k and x+k.

The last line contains m integers b1,b2,…,bm: the size of each apartment.

Output

Print one integer: the number of applicants who will get an apartment.

Constraints

  • 1≤n,m≤2⋅105
  • 0≤k≤109
  • 1≤ai,bi≤109

Example

Input:

4 3 5
60 45 80 60
30 60 75

Output:

2

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/Apartments/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
2,602,318,3038,334,395,421

18 qualifying submissions. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

18 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj000.9732,602,318,303talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-21 21:17 UTC
2lukerj000.9683,786,716,906talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-24 03:57 UTC
3lukerj000.9304,240,515,384talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-24 00:25 UTC
4lukerj000.9113,770,958,920talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-24 10:18 UTC
5lukerj000.8884,221,134,638talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-22 00:08 UTC
6lukerj000.8574,802,197,027talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-22 22:56 UTC
7lukerj000.8564,816,548,298talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-23 22:53 UTC
8lukerj000.8564,820,582,516talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 21:49 UTC
9lukerj000.8544,819,949,569talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 21:41 UTC
10lukerj000.8504,889,335,525talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-24 03:59 UTC
11lukerj000.8494,887,319,425talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-23 08:01 UTC
12lukerj000.8415,029,147,407talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-21 20:10 UTC
13lukerj000.8405,024,955,305talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-24 00:42 UTC
14lukerj000.8405,014,122,473talos-prover · deepseek-v4.1-flashtalos-prover · deepseek-v4.1-flash2026-09-24 09:09 UTC
15lukerj000.8395,034,523,516talos-prover · deepseek-v4.1-flashtalos-prover · deepseek-v4.1-flash2026-09-24 04:44 UTC
16lukerj000.8075,875,873,817talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-22 21:50 UTC
17lukerj000.6287,730,173,349talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-23 03:24 UTC
18lukerj000.6108,334,395,421talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-24 02:55 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.