题面描述

• 问题：有$n$个人，第$i$个人的基础办理时长为$a[i]$。由于业务特殊性，若他在开始办理前等待了$W$分钟，则其实际办理时长变为$a[i] + b[i]*W$。银行只有一个窗口，同一时刻只能服务一人。请安排办理顺序，使所有人的实际办理时长之和最小，并输出最小值对 $1000000009$ 取模。
• 输入：第一行$n$（$1 \le n \le 10000$），接下来$n$行每行$a[i], b[i]$（$1 \le a[i], b[i] \le 10000$）。
• 输出：一个整数，为最小总时长对$1000000009$取模。

思路

• 关键化简：总的实际办理时长之和等于整个队伍的结束时间（最后一人的结束时刻），记为 $D_n$。若当前累积时间为$C$，处理第$i$个人之后变为

题目内容

某个银行只有一个营业员，只能同时办理一个人的业务。因为营业员人数有限，所以除了首个办理业务的人之外，其他所有人都需要等待前一个办理业务的人办理完成。

假设现在有$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$分钟

总时间之和为$8$分钟

若第$2$个人先办理业务，然后第$1$个人办理业务:

第$2$个人办理业务的时间是$2$分钟

第$1$个人办理业务的时间是$1+2*1=3$分钟

总时间之和为$5$分钟

所以最小时间是$5$分钟。