TopCoder

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

69.2% (9/13)

Tags

Description

有$N$隻牛,沿著草原排隊,其中第$i$隻牛站在x座標為$x_i$的位置上,而每隻牛都有一個音量值$v_i$,即若兩隻牛$i$與$j$要交談的話,至少需要$max(v_i,v_j)\times\lvert x_i-x_j\rvert$分貝的音量。
現在請你統計,所有可能的$\frac{N(N-1)}{2}$組交談的分貝總合至少為多少。

Input Format

輸入第一行包含正整數$T(T\le 10)$,代表有幾組測資。
每一筆測資第一行包含一個正整數$N(N\le 20000)$,代表有幾頭牛。
接著$N$行每行有兩個正整數$v_i,x_i(x_i,v_i\le 20000)$,代表第$i$頭牛的音量值以及位置。

Testdata Score Constraint
Subtask 1 0~0 17 $N\le10$
Subtask 2 1~1 20 $N\le100$
Subtask 3 2~2 25 $N\le1000$
Subtask 4 3~3 38 $N\le20000$

Output Format

對於每組測資,輸出全部可能的交談的分貝總和

Sample Input

1
4
3 1
2 5
2 6
4 3

Sample Output

57

Hints

保證沒有兩頭牛站在同一個位置上。

Problem Source

Subtasks

For Testdata: 0 ~ 0, Score: 17
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 25
For Testdata: 3 ~ 3, Score: 38
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536