409736: GYM103714 F Шахматы безумия

F. Шахматы безумияограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Четыре друга, Артём, Юджин, Евгений и Влад, решили сыграть партию в шахматы. Как мы знаем, вчетвером в обычные шахматы сыграть нельзя, поэтому компания решила сыграть партию в «Безумные шахматы».

Смысл игры прост — игроки делятся на пары и играют в обычные шахматы, но с одним условием. Фигуры, выигранные вашим союзником, передаются вам. Чтобы их выставить на поле, необходимо потратить ход. Эти фигуры можно размещать в любом месте на доске.

Друзья разделились на пары. Юджин играет против Евгения в одной команде с Владом, а Артем играет против Влада в одной команде с Евгением.

Влад безумно хорош в шахматах, поэтому он уже победил Артема и передал все его фигуры Юджину. Теперь перед Юджином стоит задача победить своего противника. Для этого необходимо обменять все фигуры Евгения. Обмен фигур возможен, только если сила фигуры Юджина превосходит силу фигуры Евгения на $$$D$$$ или более.

Помогите Юджину победить Евгения за минимальное количество ходов. За один ход Юджин может обменять одну свою фигуру на фигуру оппонента или выставить одну из фигур Артёма.

Да начнется шахматное безумие!

Входные данные

Первая строка входных данных содержит четыре целых числа $$$n$$$, $$$m$$$, $$$k$$$ и $$$D$$$ ($$$1 \le n, m, k \le 10^5, 1 \le D \le 10^9$$$) — количество фигур у Юджина, количество фигур у Евгения, количество фигур у Артёма и количество очков $$$D$$$.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — сила фигур Юджина.

Третья строка содержит $$$m$$$ целых чисел $$$b_i$$$ ($$$1 \le b_i \le 10^9$$$) — сила фигур Евгения.

Четвертая строка входных данных содержит $$$k$$$ целых чисел $$$c_i$$$ ($$$1 \le c_i \le 10^9$$$) — сила фигур Артёма.

Выходные данные

Выведите единственное число — минимальное количество ходов, которое нужно сделать Юджину, чтобы победить Евгения. Если Юджин не может победить, выведите $$$-1$$$.

ПримерыВходные данные

3 4 2 3
5 4 12
14 1 2 8
6 17

Выходные данные

5

Входные данные

3 1 2 1
5 7 5
8
3 2

Выходные данные

-1