TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

88.6% (31/35)

Submission's AC Ratio

30.7% (70/228)

Tags

Description

你用了俄羅斯娃娃許了願,然而俄羅斯娃娃們因法力不支(?)而紛紛倒下了。被這魔力深深吸引的你,決定好要去尋找其它擁有法力的俄羅斯娃娃繼續許願。

要知道,俄羅斯娃娃的法力不是由單一一個俄羅斯娃娃決定的,而是由一堆俄羅斯娃娃們之間的相互作用所決定的。
一堆俄羅斯娃娃的法力總和的計算方法也非常簡單:對於每對滿足$A$放得進$B$的相異俄羅斯娃娃$A,B$(這裡只要求寬和高大於等於另一個的寬和高),他們所貢獻的法力大小即為在$B$內放入$A$後所剩的空間大小。也就是說,法力總和等於
$$ \sum_{w_i \leq w_j, h_i \leq h_j, i\neq j} w_jh_j-w_ih_i$$

你到了一間俄羅斯娃娃店,看到了一組又一組的俄羅斯娃娃。當然,你想要找到法力最高強的那組俄羅斯娃娃。為此,你想要用程式幫助你計算給定的俄羅斯娃娃們的法力總和。

Input Format

第一行有一個正整數$N\leq 10^ 6$,代表俄羅斯娃娃的個數。
接下來的$N$行中,每一行會有兩個正整數$w_i, h_i\leq 10^ 9$,代表這個俄羅斯娃娃的寬跟高。

子任務(測資) 額外限制 分數
1 (0~4) $N\leq 10^ 4$ 8
2 (5~9) $N\leq 10^ 5$ 46
3 (10~14) 無限制 46

Output Format

請輸出一個數字,代表這堆俄羅斯娃娃的法力大小。
由於答案有可能很大,請將答案模1000000009後輸出。

Sample Input 1

3
1 1
3 4
5 2

Sample Output 1

20

Hints

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第三次模擬賽pB

Subtasks

No. Testdata Range Score
1 0~4 8
2 5~9 46
3 10~14 46

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 2000 131072 262144 3
11 2000 131072 262144 3
12 2000 131072 262144 3
13 2000 131072 262144 3
14 2000 131072 262144 3