题目描述(ID:12102)
标题: 未名湖钓鱼
标签: 贪心
详情: 在校园里,有一群没有命名小湖,那里有山有水,小湖里都有很多鱼,而且这些小湖都是排列在一条直线上的。有一天小明去湖里钓鱼,他想钓到更多的鱼,可是他的时间是有限的,没有办法的小明只好通过电话求助你,让你帮他算一下他最多可以钓到多少鱼。



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

输入格式:
第一行,四个数,N,M,T,K。
第 2 至第 n+1 行,每行两个数,分别表示了这 N 个湖的初始鱼数量和每钓一次减少的鱼的数量,即 s[i],c[i]。
输出格式:
一个数,小明可以钓到的最多的鱼的数量。
限制: 对于 30%的数据,N<=100,M<=100,T<=100,K<=100。
对于 100%的数据,N<=5000,M<=100000,T<=100,K<=1000,S<=10000,C<=1000。
样例:

输入

3 12 2 2
10 2
9 1
15 5

输出

35

解释

小明一开始在第一个湖,钓一次鱼。之后到第三个湖,钓两次鱼。结果为 10+15+10=35
登录并解答