The Ravagers' Treasure Hunt

hard
The Ravagers, a group of space mercenaries, have discovered information about several treasure vaults across the galaxy. Yondu needs to assign his crew members to raid these vaults efficiently.
There are $n$ treasure vaults and $m$ crew members. Each vault has a security level represented in a $0$-indexed integer array $v$, with the $i^{th}$ vault requiring $v_i$ skill to break into. The skill level of each crew member is stored in a $0$-indexed integer array $r$, with the $j^{th}$ crew member having $r_j$ skill level. Each crew member can only be assigned to a single vault and must have a skill level greater than or equal to the vault's security level (i.e., $r_j \geq v_i$).
Yondu also has $b$ special tech boosters that will increase a crew member's skill by $e$. He can decide which crew members receive these boosters; however, each crew member may receive at most one booster.
Given the $0$-indexed integer arrays $v$ and $r$ and the integers $b$ and $e$, return the maximum number of vaults that can be raided.

Input Format:

The first line of input contains two integers $n$ and $m$ $(1 \leq n \leq 10^5$ and $1 \leq m \leq 10^5)$, the number of vaults and ravagers respectively. The second line contains two integers: the number of $b$ $(0 \leq b \leq m)$ and $e$ $(1 \leq e \leq 10^9)$. The third line contains $n$ integers $v_1, v_2, \dots, v_n$ representing the vaults. $(1 \leq v_i < 10^9)$ The fourth line contains $m$ integers $r_1, r_2, \dots, r_m$ representing the ravagers. $(1 \leq r_i \leq 10^9)$

Output Format:

Output a single integer representing the maximum number of vaults that can be raided.

Examples:

Example 1:

Input:

3 3
1 1
3 2 1
0 3 3

Output:

3

Example 2:

Input:

2 3
1 5
5 4
0 0 0

Output:

1

Code

Loading Editor...