题目内容

一位工匠需要依次处理今天收到的 $n$ 个订单。所有订单同时到达，工匠一次只能处理一个订单。每个订单 $i$ 有两个参数：基准工时 $a_i$ 和拖期敏感系数 $b_i$。如果某一订单在开始处理前已经累计等待了 $W$ 分钟（$W$ 等于排在它之前的所有订单的完工时间之和），则该订单的实际处理时间将从基准工时延长为 $a_i + b_i \times W$。

订单 $i$ 的总耗时定义为从下单到完工所经历的全部时间，即等待时间 $W$ 加上实际处理时间，因此总耗时为 $a_i + (1+b_i) \times W$。

请你安排订单的处理顺序，使得所有订单的总耗时之和尽可能小，并输出这个最小值。由于答案可能很大，请对 $1000000009$ 取模后输出。

订单数量 $n$ 不超过 $10000$，基准工时 $a_i$ 和拖期敏感系数 $b_i$ 均为不超过 $10000$ 的正整数。

输入描述

第一行包含一个整数 $n$，表示订单数量。 接下来 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$，依次表示第 $i$ 个订单的基准工时和拖期敏感系数。

输出描述

输出一个整数，表示最小的总耗时之和，对 $1000000009$ 取模的结果。

样例1

输入

1
10 20

输出

10

说明

只有一个订单，等待时间 $W=0$。 该订单的总耗时为 $a_1 + (1+b_1) \times W = 10 + (1+20) \times 0 = 10$。 因此最小的总耗时之和为 10。

样例2

输入

3
2 3
3 2
5 1

输出

23

说明

首先按 $a_i/b_i$ 升序排列订单： 订单 1：$a_1=2,\ b_1=3$，$a_1/b_1 \approx 0.667$； 订单 2：$a_2=3,\ b_2=2$，$a_2/b_2 = 1.5$； 订单 3：$a_3=5,\ b_3=1$，$a_3/b_3 = 5$。 最优处理顺序为 $(2,3) \to (3,2) \to (5,1)$。 依次计算累计时间： 初始 $cur = 0$。 处理 $(2,3)$：$cur = 2 + (1+3) \times 0 = 2$。 处理 $(3,2)$：$cur = 3 + (1+2) \times 2 = 9$。 处理 $(5,1)$：$cur = 5 + (1+1) \times 9 = 23$。 最终 $cur = 23$，即为最小的总耗时之和。

样例3

输入

2
2 1
4 2

输出

10

说明

两个订单的 $a_i/b_i$ 均为 $2$。 当比值相等时，按 $b_i$ 升序排列，即 $(2,1)$ 先于 $(4,2)$ 处理。 最优顺序为 $(2,1) \to (4,2)$。 初始 $cur = 0$。 处理 $(2,1)$：$cur = 2 + (1+1) \times 0 = 2$。 处理 $(4,2)$：$cur = 4 + (1+2) \times 2 = 10$。 最小的总耗时之和为 10。