Responsive image

问题 H: 英雄

问题 H: 英雄

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

题目描述

当你在玩游戏的时候，你的队友全部阵亡，现在你需要消灭全部敌人，
来获得胜利。在游戏中有两个关健的属性：生命值和攻击力，
你的英雄的生命几乎是无限的，但攻击力只有1。
为了简化问题，我们假设游戏回合制的，不是实时的。每一轮中你可以选择
攻击一个英雄，他的生命值会减少1。同时所有的敌人英雄会攻击你。你的
生命值会减少他们攻击力之和。如果一个英雄的HP下降为零，他会死亡。
在下一轮他将不能攻击。
虽然你的英雄几乎是无敌的，但你还要选择一个生命值减少最少的策略。

输入描述

每组测试数据的第一行包含敌人数n(1<= n <= 20)。然后n行hp，dps
表示敌人的生命值和攻击力(1<=hp<=1000, 1<=dps<=1000)。

输出描述

输出一行测试数据，表示最低生命值损失。

样例输入

1
10 2
2
100 1
1 100

样例输出

20
201
[提交][状态]
ACM算法攻关部