TopCoder

Thumb 3ac79f3df8dcd1001410d90a738b4710b9122f08
矢澤にこ
にっこにっこにー♪ あなたのハートににこにこにー♪ 笑顔届ける矢澤にこにこー♪ にこにーって覚えてラブにこー♪

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

45.7% (16/35)

Description

小美冰淇淋將要遊覽一個有N個島嶼的公園。從每一個島i出發,只建造一座橋。橋的長度以Li表示。公園內總共有N座橋。儘管每座橋由一個島連到另一個島,但每座橋均可以雙向行走。同時,每一對這樣的島嶼,都有一艘專用的往來兩島之間的渡船。

相對於乘船而言,小美冰淇淋更喜歡步行(雖然他錢很多,但是他還是想要運動一下)。小美冰淇淋希望所經過的橋的總長度盡可能的長,但受到以下的限制。
  • 可以自行挑選一個島開始遊覽。
  • 任何一個島都不能遊覽一次以上。
  • 無論任何時間都可以由你現在所在的島S去另一個從未到過的島D。由S到D可以有以下方法:
    o 步行:僅當兩個島之間有一座橋時才有可能。對於這種情況,橋的長度會累加到步行的總距離;或者
    o 渡船:可以選擇這種方法,僅當沒有任何橋和/或以前使用過的渡船的組合可以由S走到D(當檢查是否可到達時,應考慮所有的路徑,包括經過曾遊覽過的那些島)。

注意,小美冰淇淋不必遊覽所有的島,也可能無法走完所有的橋。

身為小美冰淇淋的好碰友,你,需要編寫一個程序,給定N座橋以及它們的長度,按照上述的規則,計算小美冰淇淋可以走過的橋的最大長度。

•2 <= N <= 1,000,000,公園內的島嶼數目。
•1<= Li <= 100,000,000,橋i的長度。

Input Format

第一行包含N個整數,即公園內島嶼的數目。島嶼由1到N編號。

隨後的N行每一行用來表示一個島。第i 行由兩個以單空格分隔的整數,表示由島i築的橋。第一個整數表示橋另一端的島,第二個整數表示該橋的長度Li。你可以假設對於每座橋,其端點總是位於不同的島上。

Output Format

你的程序必須向標準輸出寫出包含一個整數的單一行,即可能的最大步行距離。

Sample Input

7
3 8
7 2
4 2
1 4
1 9
3 4
2 3

Sample Output

24

Hints

最後...冰淇淋融化了

Problem Source

HOJ

Subtasks

For Testdata: 0 ~ 20, Score: 100
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
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 262144 65536
17 1000 262144 65536
18 1000 262144 65536
19 1000 262144 65536
20 1000 262144 65536