Có \(n\) người xin thuê nhà và \(m\) căn hộ trống. Nhiệm vụ của bạn là phân phối các căn hộ sao cho có nhiều người xin thuê nhất có thể nhận được một căn hộ.
Mỗi người xin thuê có một diện tích căn hộ mong muốn, và họ sẽ chấp nhận bất kỳ căn hộ nào có diện tích đủ gần với diện tích mong muốn.
Yêu cầu. Hãy phân phối các căn hộ cho người xin thuê sao cho số người nhận được căn hộ là lớn nhất có thể, và in ra số lượng đó.
\InputFile
Dòng đầu tiên chứa ba số nguyên \(n\), \(m\), \(k\) --- lần lượt là số người xin thuê nhà, số căn hộ trống, và độ chênh lệch tối đa cho phép.
Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) --- diện tích mong muốn của từng người xin thuê. Nếu diện tích mong muốn của một người là \(x\), người đó sẽ chấp nhận bất kỳ căn hộ nào có diện tích nằm trong đoạn \([x-k, x+k]\).
Dòng thứ ba chứa \(m\) số nguyên \(b_1, b_2, \ldots, b_m\) --- diện tích của từng căn hộ.
- \(1 \le n, m \le 2 \times 10^5\);
- \(0 \le k \le 10^9\);
- \(1 \le a_i, b_i \le 10^9\).
\OutputFile
In ra một số nguyên duy nhất --- số lượng người xin thuê sẽ nhận được căn hộ, khi việc phân phối được thực hiện một cách tối ưu.
\Examples
\beginexample
\exmp
4 3 5
60 45 80 60
30 60 75
2
\endexample
\Note
Trong ví dụ, người có nhu cầu \(60\) có thể nhận căn hộ diện tích \(60\) (chênh lệch \(0\)), và người có nhu cầu \(80\) có thể nhận căn hộ diện tích \(75\) (chênh lệch \(5 \le k\)). Căn hộ diện tích \(30\) không phù hợp với ai, và người có nhu cầu \(45\) không có căn hộ nào phù hợp. Vậy tối đa có \(2\) người nhận được căn hộ.
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.