Assistant Ranking
시간 제한1초메모리 제한512 MB
N개의 점 (a_i, b_i)와 한계 K가 주어질 때, a_i + K < a_j 또는 b_i + K < b_j이면 j가 i보다 낮은 순위가 아니어야 한다는 조건 아래 서로 다른 순위의 최대 개수를 구한다.
문제
The online retailer Amagoogsoftbook currently offers different so-called ``home assistants'', which it wants to recommend to its customers. For this recommendation, they wish to rank all the assistants. The quality of this ranking is not very important -- multiple assistants may even be assigned the same rank -- but they wish to maximize the number of distinct ranks assigned, to lessen the decision fatigue of their customers.
To ensure that the ranking is not completely arbitrary, they have collected for each assistant two measurements and -- the quality of the jokes the assistant can tell and how nice are the compliments the assistant is able to give (clearly these are the two most important aspects). These measurements are of course somewhat subjective, so we wish to ignore small differences in them. However, if for two given assistants and we have that or , the ranking of assistant must be the same or higher than the ranking of assistant . This rule may force two products to be given the same ranking, for example if an assistant gives much better puns than assistant , while assistant gives the superior self-esteem boosts.
What is the maximum number of distinct ranks, taken over all possible rankings?
입력
The first line contains the integers and -- the number of assistants and the measurement difference limit as described in the statement. The next line contains the integers . The next line contains the integers .
All measurements are between and .
출력
Output a single integer: the maximum number of distinct ranks.