408508: GYM103176 A A Billionaire

A. A Billionairetime limit per test0.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputI wanna be a Billionaire so bad, Buy all of the things I never had.Billionaire Travie McCoy ft. Bruno Mars

Alice is a big fan of Burno Mars. After she listened to Burno Mars' song "Billionaire", she also wants to buy a lot of things she wants.

Despite wanna buy a lot of luxuries, Alice is not a billionaire at this moment. Currently, Alice just has $$$K$$$ dollars. Luckily, she is a genius in investment, she can earn exactly $$$E$$$ dollars per day! She plans to use her income and savings to buy the luxuries she wants starting from tomorrow (day 1).

Alice finds that there are $$$N$$$ luxury items she wants to buy. The $$$i$$$-th item is priced at $$$c_i$$$ dollars. Undoubtedly, Alice is going to buy all of them! However, she also needs to limit her expenditure every day. Therefore, Alice decides not to buy more than one item on a single day. To buy the item $$$i$$$ on some day, Alice needs to have at least $$$c_i$$$ dollars on that day. In other words, her wealth is not allowed to be negative at any moment. She can also choose not to buy on some days such that she can accumulate her money earned and buy something more expensive later. Now, Alice is curious to know what is the minimum number of days such that she can obtain all $$$N$$$ luxury items. Note that Alice is not necessary to buy the luxury items in order.

Input

The first line contains 3 integers, $$$N$$$, $$$K$$$, $$$E$$$, representing the number of luxury items Alice wants to buy, the money she has at the beginning and the money she earns per day.

The second line contains $$$N$$$ integers, $$$c_i$$$, representing the price of the $$$i$$$-th item.

It is guaranteed that $$$1 \leq N \leq 200 $$$ and $$$1 \leq K, E, c_i \leq 10^7$$$

Output

Output an integer in a single line, which is the minimum number of days such that Alice can obtain all $$$N$$$ items.

ExamplesInput

3 2 2
4 5 3

Output

5

Input

2 10 10
5 5

Output

2

Note

In sample 1, Alice may buy the $$$2$$$-nd item, which is $$$5$$$ dollars, on day 2 as she will have $$$2 + 2 \times 2 = 6$$$ dollars on that day. She will have $$$1$$$ dollar remaining after buying it. Then Alice may buy the $$$3$$$-rd item on day 3 and the $$$1$$$-st item on day 5.