Bester Matcher
Du hast dich entschieden, eine einfachste Version einer Dating-App zu programmieren. Dazu sammelst du die Körpergrößen der Personen in Gruppe A als und die Körpergrößen der Personen in Gruppe B als . Du möchtest so viele Paare wie möglich zusammenbringen (jede Person kann nur einmal zugeordnet werden). Dabei gehst du davon aus, dass ein Paar zufrieden ist, wenn:
- Die Person aus Gruppe B nicht kleiner ist als die Person aus Gruppe A um mehr als
xund
- Die Person aus Gruppe B nicht größer ist als die Person aus Gruppe A um mehr als
y.
Dein Ziel ist es, die maximale Anzahl dieser Paare zu finden.
Eingabe
Die erste Zeile der Eingabe enthält 4 ganze Zahlen
n, m (1 ≤ n, m ≤ ), x und y (0 ≤ x, y ≤ ) – die Anzahl der Personen in Gruppe A, die Anzahl der Personen in Gruppe B sowie die beiden Grenzwerte für akzeptable Größenunterschiede.
Die nächste Zeile enthält n Ganzzahlen , die die Körpergrößen der Personen in Gruppe A darstellen (1 ≤ ≤ ).
Die darauffolgende Zeile enthält m Ganzzahlen , die die Körpergrößen der Personen in Gruppe B darstellen (1 ≤ ≤ ).Ausgabe
Das Programm soll die maximale Anzahl passender Paare ausgeben.
Beispiele
Eingabe | Ausgabe |
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: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB