A7362. [USACO07JAN] Protecting the Flowers S
编程题
普及/提高-
知识点
题目描述
有 $n$ 头奶牛跑到 FJ 的花园里去吃花儿了。
第 $i$ 头奶牛在距离牛圈 $T_i$ 的地方吃花，这里的 $T_i$ 表示 FJ 从牛圈到这头奶牛所在位置需要 $T_i$ 分钟。
第 $i$ 头奶牛每分钟会吃掉 $D_i$ 朵花。
FJ 现在要将这些奶牛赶回牛圈，但是他每次只能赶一头牛回去。
如果赶第 $i$ 头牛回牛圈，来回总共需要 $2\times T_i$ 分钟。
在这段时间内，其它还没有被赶回牛圈的奶牛会继续吃花，速度保持不变。
正在被赶回牛圈的奶牛不会继续吃花。
请你求出，在最优安排下，所有奶牛一共吃掉的花的最小数量。
第 $i$ 头奶牛在距离牛圈 $T_i$ 的地方吃花，这里的 $T_i$ 表示 FJ 从牛圈到这头奶牛所在位置需要 $T_i$ 分钟。
第 $i$ 头奶牛每分钟会吃掉 $D_i$ 朵花。
FJ 现在要将这些奶牛赶回牛圈，但是他每次只能赶一头牛回去。
如果赶第 $i$ 头牛回牛圈，来回总共需要 $2\times T_i$ 分钟。
在这段时间内，其它还没有被赶回牛圈的奶牛会继续吃花，速度保持不变。
正在被赶回牛圈的奶牛不会继续吃花。
请你求出，在最优安排下，所有奶牛一共吃掉的花的最小数量。
输入格式
第一行一个正整数 $n$。
接下来 $n$ 行，每行两个正整数 $T_i,D_i$。
接下来 $n$ 行，每行两个正整数 $T_i,D_i$。
输出格式
输出一行一个整数，表示答案。
输入输出样例
输入 #1
6 3 1 2 5 2 3 3 2 4 1 1 6
输出 #1
86
说明/提示
## 样例解释
最优策略是按照 $6\to 2\to 3\to 4\to 1\to 5$ 的顺序把牛赶回牛圈。
## 数据范围
对于 $100\%$ 的数据：
$1\le n\le 10^5$
$1\le T_i\le 2\times 10^6$
$1\le D_i\le 100$
最优策略是按照 $6\to 2\to 3\to 4\to 1\to 5$ 的顺序把牛赶回牛圈。
## 数据范围
对于 $100\%$ 的数据：
$1\le n\le 10^5$
$1\le T_i\le 2\times 10^6$
$1\le D_i\le 100$