Algorithms and Data Structures

Best matcher

You’ve decided to implement the simplest version of a dating app. For that, you’ve decided to collect the heights of individuals in Group A as and the heights of individuals in Group B as You’ve decided to match as many pairs as possible (one person can only be matched once). And you think that couples will be okay if:
  • The person from Group B is not shorter than the person from Group A by x and
  • The person from Group B is not taller than the person from Group A by more than y.
You’d like to match as many pairs as possible.

Input

The first line of the input contains 4 integers n, m (1 ≤ n, m ≤ ), x, and y (0 ≤ x, y ≤ ) - the number of individuals in Group A, the number of individuals in Group B, and the bounds for acceptable heights. The next line contains n integers representing the heights of the individuals in Group A (1 ≤ ≤ ). The line after that contains m integers representing the heights of the individuals in Group B (1 ≤ ≤ ).

Output

The program should print the maximum number of pairs matched.

Examples

Input
Output
6 2 0 0 1 2 3 4 5 6 6 7
1
3 3 1 1 4 5 6 3 4 7
3
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue