题面描述

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