OI题库

1 未名湖钓鱼(fish)


【背景】
在校园里，有一群没有命名小湖，那里有山有水，小湖里都有很多鱼，而且这些小湖都
是排列在一条直线上的。
有一天小明去湖里钓鱼，他想钓到更多的鱼，可是他的时间是有限的，没有办法的小明
只好通过电话求助你，让你帮他算一下他最多可以钓到多少鱼。


【题目描述】
现在有N 个未名小湖排在一条直线上，相邻两个小湖之间的距离是相等的，需要T 分
钟的步行才可以到达相邻的一个小湖。每个湖刚开始的时候都会有一些鱼，未名湖神奇就神
奇在，你钓一次就可以把当前所有的鱼全部钓上来，但是湖中的鱼只会减少一个固定的数值，
而且消耗一个固定的时间K，如果当前湖中的鱼小于这个数值，则会把剩下的所有的鱼全部
钓上来，之后湖中的鱼归零。（如果钓鱼后减少的具体过程不明白，请参照样例）对于第i
个小湖，初始的鱼的数量记作s[i]，每钓一次会减少c[i]。小明只有M 的时间，他希望你能
在最短的时间内算出他最多可以钓多少鱼。当然，小明刚开始的时候在第一个湖的位置，并
且他希望在用光时间之前到达第N 个湖的位置(注意在钓鱼结束前小明必须在第n 个湖，并
且剩下的时间大于0)，之后结束他的钓鱼之旅。


【输入数据】
第一行，四个数，N,M,T,K。
第2 至第n+1 行，每行两个数，分别表示了这N 个湖的初始鱼数量和每钓一次减少的
鱼的数量，即s[i],c[i]。


【输出数据】
一个数，小明可以钓到的最多的鱼的数量。


【输入样例】
3 12 2 2
10 2
9 1
15 5


【输出样例】
35


【样例说明】
小明一开始在第一个湖，钓一次鱼。之后到第三个湖，钓两次鱼。结果为10+15+10=35


【数据范围】
对于30%的数据，N<=100,M<=100,T<=100,K<=100。

对于100%的数据，N<=5000,M<=100000,T<=100,K<=1000，S<=10000,C<=1000。

湖北省NOIP2011寒假集训Day5