Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Crypto Gift

By TarikHassan, ash_98 · Limits 1s, 512 MB

Professor invites his nn friends on his birthday. He wants to reward all of them and make them happy. The ithi^{th}friend will be happy if the friend gets at least AiA_i units of cryptocurrency coins.

Professor is hiring nn miners and they are capable of mining xx cryptocurrency coins per unit time. Professor is also a special cryptocurrency miner and he can mine yy cryptocurrency coins per unit time. So there is a total of n+1n+1 miners including the Professor.

At each unit time, Professor distributes the cryptocurrencies among his friends. The distribution procedure is as follows:

  • A friend can have coins only from a single miner or no coins at all. That means, when the Professor gives coins to a friend at a particular time, the friend cannot have coins from the other source at that time unit.

  • Coins mined by a miner can not be split up i.e. if the Professor chooses to give miner AA’s coins to a friend FF, then FF gets all the coins mined by AA at this unit time.

  • Unused coins will be lost and can not be used in the next round.

Now you have to answer the minimum units of time needed for the Professor to fulfill all his friends’ requirements.

Input

The first line contains one integer n(1n2×105)n (1\leq n\leq 2\times10^5 ) denoting the number of Professor’s friends.

Second line contains n elements A1,A2,....,An(1Ai109)A_1,A_2,....,A_n (1\leq A_i\leq 10^{9}) number of cryptocurrency coins needed for ithi_{th} friends.

The next line contains two integer x, y (1x,y109)(1\leq x, y\leq10^{9}), the number of cryptocurrency coins mined per unit time by the miners and number of cryptocurrency coins mined per unit time by the Professor respectively.

Output

Print a single line indicating the minimum number of time needed so that the Professor can fulfill all of his friends’ requirements.

Samples

InputOutput
3
3 5 6
1 3
3

Initial requirement [3,5,6]

Time -1: [2,4,3], Professor gave his cryptocurrency coin to friend-3, other friends took from general miners.

Time-2: [1,3,0], Professor gave his cryptocurrency coin to friend-3, other friends took from general miners.

Time-3: [0,0,0], Professor gave his cryptocurrency coin to friend-2, other friends took from general miners.

InputOutput
3
6 10 5
9 9
2

Discussion

Statistics


56% Solution Ratio

naeem4265Earliest, 1M ago

HSTU_TREENITYFastest, 0.0s

serotoninLightest, 967 kB

fahimcp495Shortest, 727B

Submit

Login to submit

Editorial

Suppose total t unit time needed to fulfill all his friend’s requirements. Now how can we check that...

Toph uses cookies. By continuing you agree to our Cookie Policy.