Bus Wheels (1 Point)

Bus Wheels

m wheels on the bus go round and round,

breaking down,

breaking down.

n wheels on the bus are lying around,

All the way to town.

The $m$ -wheeled school bus is taking an extremely long journey on a very bumpy road. Unforunately you haven't got the budget for an all-terrain school bus, and so your wheels are looking worse for wear.

Luckily, the bus is carrying no children, which leaves a lot of space for spare wheels!

You are trying to drive as far as possible, however each of your $n$ wheels is rated for a particular distance $k$ metres, after which they will break. Each wheel that breaks then needs to be replaced, which takes $t$ seconds per wheel. It doesn't take any time to begin putting the initial $m$ wheels on your bus.

The bus travels at 1m/s, and you want to maximise how far you've travelled after $x$ seconds.

Input

Input will begin with 4 space-separated integers, $n, m, t, x$ , which are:

The number of wheels in your possession
The number of wheels the bus requires to move
The time it takes to replace a single wheel
The time we have to travel as far as possible

A second line containing $n$ space-separated integers will follow, representing the distance rating for each of the $n$ wheels.

Output

Output a single integer, the furthest your bus can travel after $x$ seconds.

Constraints

$1 \leq n \leq 10^5$
$1 \leq m \leq 20$
$1 \leq t \leq 10^6$
$1 \leq x \leq 10^{15}$
$1 \leq k \leq 10^8$ (Distance rating)

Example

For the input

Sample 1

10 4 3 15
8 3 5 7 3 2 1 3 5 6

The correct output would be 7. This is because we can travel 7 metres by starting off with these 4 wheels to begin:

8 7 5 5

Then, after travelling for 5 metres, two wheels need replacing, taking 6 seconds. We replace these with wheels of length 3 and 2 (Both taking 3 seconds to replace).

8 7 3 2

After another 2 metres travelled, the 7 wheel and 2 wheel both need replacing, but by this point we've already taken 13 seconds, so replacing these two wheels would take us over 15 seconds.