描述

当你和神一样的对手和猪一样的队员一起玩游戏时，你必须面对一个尴尬的情况：你的所有队友都被杀了，你必须打 1vN 游戏中的英雄有两个关键属性，生命值（HP）和每发伤害（DPS）。你的英雄拥有几乎无限的生命值，但 DPS为1. 为了简化问题，我们假设游戏是回合制的，但不是实时的。在每回合中，你可以选择一个敌方英雄进行攻击，每攻击一下他的生命值将减少 1。同时，所有活着的敌方英雄都会攻击你，你的生命值会减少他们 DPS 的总和。如果一个英雄的生命值等于（或低于）零，他将在本轮之后死亡，并且在接下来的几轮中无法攻击你 虽然你的英雄是不败的，但你想选择最佳策略，以最小的生命损失杀死所有敌人。

输入描述

每个测试用例的第一行包含敌方英雄的数量 N(1 <= N <= 20). 然后是N 行，每行包含两个整数 DPSi 和 HPi，这是每个英雄的 DPS 和 HP。 (1 <= DPSi, HPi <=1000)

输出描述

每次测试输出一行，表示最小 HP 损失。

用例输入 1

1 10 2 用例输出 1

20 用例输入 2

2 100 1 1 100 用例输出 2

201 用例输入 3

3 50 10 100 1 10 1 用例输出 3

720