jhljx是一个很喜欢玩卡牌的人,他总共有n张牌,每张牌都有一个英雄。
每个英雄$i$都在离家很远的地方,需要$T_{i}$分钟的时间才能回到家,当该英雄处于等待状态的时候,每分钟消耗$S_{i}$点体力。而奇怪的是英雄在回家的路上不需要消耗体力。
从每个英雄的位置到家只有一条路,也就是说每次只能有一个英雄走过。前一个英雄到家后,下一个英雄才可以开始走。
因此你需要找到这n个英雄的一个合适的顺序,保证所有英雄消耗的体力值总和最小。
输入多组数据。
对于每组数据,第一行有一个正整数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)$,分别表示英雄回家需要的时间,和英雄在等待时需要花费的体力。
对于每组数据,输出所有英雄消耗的体力总和的最小值。
6
2 5
3 1
4 1
3 2
2 3
1 6
43
POJ xxxx