题目描述
小蓝在玩游戏时遇到一个关卡,这个关卡中小明控制一个角色和怪物对打,这个角色攻击力只有1而血量是无限的,也就是说小蓝使无敌的。而每个怪物的攻击力(DPS)和血量(HP)是不同的,
为了简化问题,我们假设游戏是基于回合的,但不是实时的。在每一轮中,你可以选择一个怪物来攻击,这时他的HP会减少1;同时,所有生存的怪物都会攻击你,而你的HP会减少他们的DPS总和。如果一个怪物的HP等于(或低于)零,他将在这一轮之后死亡,并且在接下来的几轮中不能攻击你。
虽然你的英雄是不败的,但你想选择最好的策略来杀死所有敌人的英雄,同时减少自身HP的损失。
输入描述
每个测试用例的第一行包含怪物的数量N(1 <= N <= 20)。然后是N行,每行包含两个整数DPS和HP,它们是每个怪物的DPS和HP。 (1 <= DPS,HP <= 1000)
输出描述
每次测试输出一行,表示小蓝损失的最小的HP值。
样例输入
1 10 2 2 100 1 1 100
样例输出
20 201
提示