One day Tomato woke up late in the morning and realized that she had a long list of todos. Frantically, she wore her overcoat and ran outside with her bag. But, as she got out of the house and ran for the bus stop, she noticed that everything around her is snowy white. She can't figure out the foot path from the road. This is the first time she is seeing snow. ^.^
She forgot everything about her pending tasks and now she wants to make a snowman. She needs at least X amount of snow to make a snowman. Each day, she collects and piles snow fallen on that day. She can collect and store snow. However, the snow piles collected on each day melt away everyday at a fixed rate from each of the piles.
For example, she collected 10 on the 1st day and 20 on the second day, 30 on the 3rd day and the snow melts at rate 10. At the end of the 3rd day, the snow remaining on the 3 piles will be (10 - 210 = -10) = 0, (20 - 110) = 10 and (30 - 0*10) = 30. If a pile becomes <= 0, then it is discarded.
How many days will it require to make a snowman?
Note: You can assume that it's always possible to make the snowman in some day.
First line contains 3 integers N, X and D where N is the number of snowy days, X is the amount of snow required to make a snowman and D is the fixed rate of melting of snow per day. Second line contains N integers Ai where the Ai integer denotes the total snow that was collected on ith day.
1 <= N <= 100
1 <= Ai <= 1000
1 <= X <= 1000
0 <= D <= 10
sum(Ai) >= X
A single integers denoting the number of days required to make a snowman.
1 10 0 10
At the end of 1st day, 10 was collected and 10 was required to make a snowman.
3 40 10 10 20 30
As described in the problem statement.
9 128 2 3 10 31 27 7 2 65 37 4