ZOJ Problem Set - 3530
guinao is playing a PC game called Legend TD recently. There are two kinds of sources in the game, gold and wood. At the beginning of the game you will have G Gold and zero wood. You can use these gold before the first round. During the game, gold only can be collected by defending monsters, because monsters have gold with them. So when you kill a monster, you can get all the gold it has and you can use these gold in this round. Every round will come exactly one monster. Keep in mind that you can kill a monster only when your defend is equal or higher than the monster's attack and once your can't defend a monster, you will loose the game. Gold can be used to strengthen defense. The cost of increase your defense by one is one gold. In the game, the initial defense is always zero. Gold can also be used for producing farmers or increase the wooding rate. Wooding rate is the amount of wood one farmer can collect in a single round. Your farmer's initial wooding rate is W. And if you producing a farmer in this round , he will begin collecting wood from next round. The cost for producing one farmer and for increasing the wooding rate by one are both F gold. Because wood have special and great use in the game, so guinao want to collect as much wood as possible after N rounds.
There are multiple test cases. For each test case, the first line contains four integers N, F, W, G, (1<= N <= 1000, 1<= F, W <= 10000, 1<= G <= 10^6), which have been mentioned above. Then following N lines, each line contains two integers Ai, Gi (1<= Ai, Gi <= 10^6), which represents the attack of the monster comes at the i-th round and the gold it has.
Print the maximal amount of wood guinao can collect after N rounds in one line. If he can't adhere to the end of the N-th round, output "It's useless to collect wood.".
5 1 1 1 1 1 1 1 1 1 1 1 1 1 4 10 7 100 1 1 2 2 3 3 100000 4 3 10 7 10 10 10 10 10 20 10
13 It's useless to collect wood. 14
Author: YING, Yuanxiang
Contest: ZOJ Monthly, September 2011