题面描述

• 问题：有 $n$ 块符文石，第 $i$ 块的基础加工时间为 $a[i]$。由于灵气消散特性，若它在开始加工前等待了 $W$ 分钟，则其实际加工时间变为 $a[i] + b[i] \times 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$ 块符文石之后变为