Problem : 259 - Sails

Problem Statistics

Solved Member: 14　　Submission: 81　　User Tried: 17

Statement:

有一艘海盜船正在建造中。這艘船有N根船桅，每根船桅由同等長度的船桅片段所組成。每根船桅的片段數即是該根船桅的高度。每根船桅上各掛置了數片船帆，每一片船帆剛好可以掛在一個船桅片段上。船桅上的船帆可以掛在該船桅上任一船桅片段位置，但是每一船桅片段只能掛一片船帆。

不同的船帆掛置方式，受風時可產生不同的推力。某一船帆前面如有其他的船帆，該船帆受到的風力就會較小，而所能產生的推力也較小。定義每一船帆的反效率(inefficiency)為位於這片船帆後面且同等高度的船帆數。請注意「在前面」或「在後面」是跟船的方向有關，在下圖中，「前面」指的是左邊，「後面」指的是右邊。

整艘船的總反效率則為所有船帆反效率的總和。

這艘船有6根船桅，從船首（圖中左邊）到船尾每根船桅的高度分別為3, 5, 4, 2, 4, 3。這個船帆配置的方式可產生的總反效率為10。個別船帆的反效率即為圖中船帆內的數字。

Task:

請寫一個程式，當給定N個船桅的高度及船帆數時，計算出最小的總反效率。

Input:Output:

輸入的第一行有一整數N (2 ≤ N ≤ 100 000)，代表這艘船上的船桅數。接下來的N行，每行都有兩個整數，H與K (1 ≤ H ≤ 100 000, 1 ≤ K ≤ H)，分別代表每根船桅的高度與船帆數。船桅給定的順序是從船首到船尾。

佔總分25分的測試資料中，每組最多將只有1,000,000種可能的船帆配置方式。

輸出一整數，即這艘船的最小總反效率。

Sample Input:Sample Output:

6
3 2
5 3
4 1
2 1
4 3
3 2

HINT:

範例與圖片對應。

Source:

IOI 2007

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	1000ms	65536kb	8
1-2	1000ms	65536kb
2-1	1000ms	65536kb	8
2-2	1000ms	65536kb
3-1	1000ms	65536kb	9
3-2	1000ms	65536kb
4-1	1000ms	65536kb	9
4-2	1000ms	65536kb
5-1	1000ms	65536kb	9
5-2	1000ms	65536kb
6-1	1000ms	65536kb	9
6-2	1000ms	65536kb
7	1000ms	65536kb	9
8	1000ms	65536kb	9
9-1	1000ms	65536kb	10
9-2	1000ms	65536kb
10-1	1000ms	65536kb	10
10-2	1000ms	65536kb
11-1	1000ms	65536kb	10
11-2	1000ms	65536kb