问题：有 $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$ 个人之后变为

P4488.第2题-银行业务员

1000ms

Difficulty: 5

所属公司 : 京东

算法与标签>贪心算法

题目内容

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

假设现在有 $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取模(求余)

输入

2
1 1
2 5

输出

说明

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

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

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

总时间之和为 $8$ 分钟

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

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

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

总时间之和为 $5$ 分钟

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

输入

预期输出（选填）