Задача H. Horticulture ≡

Условие

Юный программист Джеймс решил заняться садоводством и принёс домой N растений в горшках.

Растение номер i изначально имеет высоту a_i и растет со скоростью v_i сантиметров в день. У Васи есть девушка, Алиса, которая пока находится в отъезде. Алиса не любит высоких растений, поэтому Вася решил время от времени обрезать растения.

Вася может уменьшить высоту любого растения только на величину равную X сантиметров (но не сделать её отрицательной) за один срез. Вася не обладает хорошей физической подготовкой, поэтому может делать не более M срезов в день. Каждый день растения вырастают после завершения всех срезов.

Алиса вернётся через T дней. Вася хотел бы обрезать растения так, чтобы к её приезду высота самого высокого растения был минимально возможной.

Формат входного файла

Первая строка входного файла содержит целые числа N, T, M, X.

Вторая строка содержит N целых чисел a_i — начальные высоты растений.

Третья строка содержит N целых чисел v_i — скорости роста растений в день.

Формат выходного файла

Выходной файл должен содержать единственное целое число — минимально возможный уровень самого высокого растения через T дней.

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ T ⋅ M ≤ 10⁵

1 ≤ X, a_i, v_i ≤ 10⁵

Примеры тестов

4 1 2 4
8 9 10 11
8 8 3 2

13

1 100000 1 100000
100000
100000

100000