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

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

Professor is hiring $n$ miners and they are capable of mining $x$ cryptocurrency coins per unit time. Professor is also a special cryptocurrency miner and he can mine $y$ cryptocurrency coins per unit time. So there is a total of $n+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 $A$’s coins to a friend $F$, then $F$ gets all the coins mined by $A$ 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.

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

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

The next line contains two integer **x, y** $(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.

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

Input | Output |
---|---|

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. |

Input | Output |
---|---|

3 6 10 5 9 9 | 2 |

56% Solution Ratio

naeem4265Earliest,

HSTU_TREENITYFastest, 0.0s

serotoninLightest, 967 kB

fahimcp495Shortest, 727B

Login to submit

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.