解题思路

设某个人前面已经排了若干人，这些人原本办理业务的总时长为 $t$。

那么这个人的最终总时间就是：

$a[i] + b[i] \times t$

其中：

题目内容

某个银行只有一个营业员，只能同时办理一个人的业务。因为营业员人数有限，所以除了首个办理业务的人之外，其他所有人都需要等待前一个办理业务的人办理完成。 假设现在有 $n$ 个人需要办理业务，第 $i$ 个人的业务需要办理 $a[i]$ 分钟。由于业务的特殊性，第 $i$ 个人每等 $1$ 分钟，他最终办理业务的时间就会多 $b[i]$ 分钟。 作为志愿者，你的任务就是安排他们的先后顺序，使每个人办理业务的总时间（包括等待时间）之和最小。

输入描述

第一行一个数 $n$，表示有 $n$ 个人（$1 <= n <= 10000$）。 接下来 $n$ 行，每行两个数 $a[i]，b[i]（1 <= a[i], b[i] <= 10000）$。

输出描述

一行一个整数，输出最小时间。如果答案过大，需要对 $1000000009$ 取模（求余）。

样例1

输入

2
1 1
2 5

输出

5

说明

若第 $1$ 个人先办理业务，然后第 $2$ 个人办理业务： 第 $1$ 个人办理业务的时间是 $1$ 分钟 第 $2$ 个人办理业务的时间是 $2 + 1*5 = 7$ 分钟 总时间之和为 $1 + 7 = 8$ 分钟 若第 $2$ 个人先办理业务，然后第 $1$ 个人办理业务： 第 $2$ 个人办理业务的时间是 $2$ 分钟 第 $1$ 个人办理业务的时间是 $1 + 2*1 = 3$ 分钟 总时间之和为 $2 + 3 = 5$ 分钟 所以最小时间是 $5$ 分钟