Author: | M. Sporyshev | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
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.
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 must contain a single integer — minimal height of the tallest plant after T days.
1 ≤ N ≤ 105
1 ≤ T ⋅ M ≤ 105
1 ≤ X, ai, vi ≤ 105
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|