Задача H. Horticulture

Автор:M. Sporyshev
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:256 Мб

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105

1 ≤ T ⋅ M ≤ 105

1 ≤ X, ai, vi ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 2 4
8 9 10 11
8 8 3 2
13
2
1 100000 1 100000
100000
100000
100000

0.024s 0.008s 9