Trong một vùng bị thiên tai, có ~n~ gia đình khó khăn cần được hỗ trợ. Mỗi gia đình có một mức nhu cầu hỗ trợ riêng được biểu diễn bằng một số nguyên dương ~a_i~ (~i = 1, 2, ..., n~). Một tổ chức cứu trợ chuẩn bị ~m~ gói quà với giá trị của mỗi gói quà được biểu diễn bằng một số nguyên dương ~b_j~ (~j = 1, 2, ..., m~) để hỗ trợ các gia đình khó khăn. Tổ chức cứu trợ sẽ phát các gói quà theo nguyên tắc: nếu mỗi gia đình có nhu cầu mong muốn là ~a_i~ thì gia đình đó sẽ nhận được chỉ một gói quà có giá trị thuộc đoạn ~[a_i - k; a_i + k]~ với ~k~ là một số nguyên không âm.
Yêu cầu: Viết chương trình giúp tổ chức cứu trợ phân chia các gói quà để phát được cho nhiều gia đình nhất.
INPUT
Dòng 1 gồm ~3~ số nguyên dương ~n, m, k~ (~1 \le n \le 2 \times 10^5;~ ~1 \le m \le n;~ ~0 \le k \le 10^5~), mỗi số cách nhau ít nhất một dấu cách.
Dòng 2 gồm ~n~ số nguyên dương ~a_i~ (~10^5 \le a_i \le 10^8; 1 \le i \le n~), mỗi số cách nhau ít nhất một dấu cách.
Dòng 3 gồm ~m~ số nguyên dương ~b_j~ (~10^5 \le b_j \le 10^8;~ ~1 \le j \le m~), mỗi số cách nhau ít nhất một dấu cách.
OUTPUT
Gồm một dòng chứa số lượng gia đình nhiều nhất nhận được các gói quà.
SAMPLE INPUT 1
4 3 5
60 45 80 90
30 60 75
SAMPLE OUTPUT 1
2
Giải thích: Vì ~k = 5~ nên có 2 gia đình nhận được gói quà phù hợp với nguyên tắc chia quà, cụ thể:
- ~01~ gia đình có nhu cầu cần hỗ trợ ~60~, giá trị gói quà ~60~
- ~01~ gia đình có nhu cầu cần hỗ trợ ~80~, giá trị gói quà ~75~
SAMPLE INPUT 2
5 2 3
21 15 35 10 40
32 16
SAMPLE OUTPUT 2
2
Giải thích: Vì ~k = 3~ nên có 2 gia đình nhận được gói quà phù hợp với nguyên tắc chia quà, cụ thể:
- ~01~ gia đình có nhu cầu cần hỗ trợ ~35~, giá trị gói quà ~32~
- ~01~ gia đình có nhu cầu cần hỗ trợ ~15~, giá trị gói quà ~16~
SUBTASKS
Subtask | Điểm | Ràng buộc |
---|---|---|
1 | ~50\%~ | ~1 \le n \le 10^4;~ ~1 \le m \le n~ |
2 | ~30\%~ | ~10^4 < n \le 10^5;~ ~10^4 < m \le n~ |
3 | ~20\%~ | ~10^5 < n \le 2 \times 10^5;~ ~10^5 < m \le n~ |
Bình luận