13012. Розселення по квартирах
Є \(n\) бажаючих і \(m\) вільних квартир. Ваше завдання - розподілити квартири так, щоб якомога більше бажаючих отримали квартиру.
У кожного заявника є бажаний розмір квартири, і вони приймуть будь-яку квартиру, розмір якої достатньо близький до бажаного.
Обмеження
- \(1 ≤ 𝑛 , 𝑚 ≤ 2 ⋅ 10^5\)
- \(0≤k≤10^9\)
- \(1≤a_i ,b_i ≤10^9\)
Формат вхідних даних
У першому рядку вхідних даних є три цілі числа \(n\), \(m\) і \(k\): кількість претендентів, кількість квартир і максимально допустима різниця.
Наступний рядок містить \(n\) цілих чисел \(a_1 , a_2 ,…, a_n\) : бажаний розмір квартири кожного претендента. Якщо бажаний розмір заявника \(x\), він або вона прийме будь-яку квартиру розміром від \(x−k\) до \(x+k\).
Останній рядок містить \(m\) цілих чисел \(b_1 , b_2 ,…,b_m\) : розміри кожної квартири.
Формат вихідних даних
Виведіть одне ціле число: кількість претендентів, які отримають квартиру.
Приклад вхідних даних
4 3 5
60 45 80 60
30 60 75
Приклад вихідних даних
2
Коментарі