Problem H. Horticulture ≡

Statement

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

Plant number i has starting height of a_i centimeters and grows by v_i 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 a_i — initial plant heights.

Third line contains N integers v_i — 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 ≤ 10⁵

1 ≤ T ⋅ M ≤ 10⁵

1 ≤ X, a_i, v_i ≤ 10⁵

Sample tests

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

13

1 100000 1 100000
100000
100000

100000