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

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.