问题 D: 巫师与恶龙(wizard)

问题 D: 巫师与恶龙(wizard)

时间限制: 1 Sec  内存限制: 256 MB
提交: 15  解决: 7
[提交] [状态] [讨论版] [命题人:]

题目描述

盘踞在中土大陆的恶龙劫持了公主小z,王国骑士的刀枪对恶龙的鳞片毫无作用。

为了拯救小z,国王请来了白抱巫师小f。

小f有一根法杖,可以施放n种法术,但是施放法术是有代价的。第i种法术将对恶龙造成vi点伤害,但是会增加小f wi的疲劳度,并缩短小f的寿命,且每种法术最多只能施放一次。而小f每积累一点疲劳度,在下一次施法的时候造成的伤害就将减少一点。

具体地说,设当前小f拥有k点疲劳度,下一次施放的法术造成的伤害原本为h点, 则由于疲劳度的影响小f只能对恶龙造成h-k点伤害。

毕竟拯救公主才是当务之急,小f一点都不在乎施放黑魔法造成寿命缩短的副作用。所以小f只关心,如何施放法术,才可以对恶龙造成尽可能多的伤害。

注意,小f没有必要施放完每一个法术,因为强行施法不但缩短寿命,还可能会给恶龙回血= =

输入

第一行包含一个整数n。

之后n行每行两个整数vi,  wi。

输出

一行一个整数,表示最优策略下小f对恶龙造成的伤害值。

样例输入 Copy

5
8 2
10 7
5 1
11 8
13 3

样例输出 Copy

27

提示

对于40%的数据,n<8

对于 100%的数据,n<5000,vi, wi<10^5