Problem H. Horticulture

Author:M. Sporyshev
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:256 Mb

Statement

Young programmer James decided to practice horticulture and brought home N plants.

Plant number i has starting height of ai centimeters and grows by vi centimeters per day. Vasya has a girlfriend Alice, who is currently traveling away from home. Alice does not like tall plants, so Vasya decided to cut his plants shorter from time to time.

Vasya can reduce height of any plant by exactly X centimeters (but not make it negative) in one cut. Vasya's endurance in not very good, so he can make no more than M cuts per day. Every day, plants grow after all cutting is finished.

Alice will return in T days. Vasya would like to cut plants in such a way as to make on the day of her arrival the height of the highest plant as small as possible.

Input file format

First line of input file contains integers N, T, M, X.

Second line contains N integers ai — initial plant heights.

Third line contains N integers vi — plant growth speeds.

Output file format

Output file must contain a single integer — minimal height of the tallest plant after T days.

Constraints

1 ≤ N ≤ 105

1 ≤ T ⋅ M ≤ 105

1 ≤ X, ai, vi ≤ 105

Sample tests

No. Input file (input.txt) Output file (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