jhljx水水的卡牌

时间限制: 2000 ms 内存限制: 65536 kb
总通过人数: 1 总提交人数: 1

Problem Description

jhljx是一个很喜欢玩卡牌的人,他总共有n张牌,每张牌都有一个英雄。

每个英雄$i$都在离家很远的地方,需要$T_{i}$分钟的时间才能回到家,当该英雄处于等待状态的时候,每分钟消耗$S_{i}$点体力。而奇怪的是英雄在回家的路上不需要消耗体力。

从每个英雄的位置到家只有一条路,也就是说每次只能有一个英雄走过。前一个英雄到家后,下一个英雄才可以开始走。

因此你需要找到这n个英雄的一个合适的顺序,保证所有英雄消耗的体力值总和最小。

Input

输入多组数据。
对于每组数据,第一行有一个正整数n($1 \leq n \leq 100000$)表示总共有n个英雄。
接下来n行,每行2个整数$T_{i}(1 \leq T_{i} \leq 1000000)$,$S_{i}(1 \leq S_{i} \leq 1000)$,分别表示英雄回家需要的时间,和英雄在等待时需要花费的体力。

Output

对于每组数据,输出所有英雄消耗的体力总和的最小值。

Sample Input

6
2 5
3 1
4 1
3 2
2 3
1 6

Sample Output

43

Source

POJ xxxx

Hint

  • greedy & sorting
  • the answer is possible to be long long
  • how to override compare function maybe a direction to you

相关推荐