Bạn đang tham quan một công viên có \(N\) hòn đảo. Từ mỗi đảo \(i\), người ta đã xây đúng một cây cầu tới một đảo khác; độ dài của cây cầu đó được ký hiệu là \(L_i\). Như vậy, công viên có tổng cộng \(N\) cây cầu. Mặc dù mỗi cây cầu được xây từ một đảo tới một đảo khác, hiện nay tất cả các cây cầu đều có thể đi theo cả hai chiều. Ngoài ra, giữa mỗi cặp đảo có đúng một tuyến phà đi lại theo cả hai chiều.

Bạn thích đi bộ hơn đi phà, nên muốn tối đa hóa tổng độ dài các cây cầu đã đi qua, đồng thời tuân thủ những quy tắc sau:

• Bạn có thể bắt đầu chuyến tham quan tại một đảo tùy ý.
• Bạn không được ghé thăm bất kỳ đảo nào quá một lần.
• Tại một thời điểm bất kỳ, bạn có thể di chuyển từ đảo hiện tại \(S\) tới một đảo \(D\) chưa từng ghé thăm, bằng một trong hai cách:
  • Đi bộ: chỉ thực hiện được khi có một cây cầu nối hai đảo. Độ dài cây cầu được cộng vào tổng quãng đường đã đi bộ.
  • Đi phà: chỉ được chọn cách này nếu không thể đi từ \(S\) tới \(D\) bằng bất kỳ cách kết hợp nào giữa các cây cầu và những tuyến phà đã sử dụng trước đó. Khi kiểm tra khả năng đi tới \(D\), phải xét mọi đường đi, kể cả những đường đi qua các đảo mà bạn đã ghé thăm.

Bạn không bắt buộc phải ghé thăm tất cả các đảo, và cũng có thể không đi qua được tất cả các cây cầu.

Cho thông tin về \(N\) cây cầu và độ dài của chúng, hãy tính tổng quãng đường đi bộ lớn nhất có thể đạt được khi tuân thủ các quy tắc trên.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\), là số đảo trong công viên. Các đảo được đánh số từ \(1\) đến \(N\).
• Mỗi dòng trong \(N\) dòng tiếp theo mô tả một cây cầu. Dòng thứ \(i\) trong số này mô tả cây cầu được xây từ đảo \(i\), gồm hai số nguyên cách nhau bởi một dấu cách: số thứ nhất là số hiệu đảo ở đầu cầu còn lại, số thứ hai là độ dài \(L_i\) của cây cầu.

Hai đầu của mỗi cây cầu luôn nằm trên hai đảo khác nhau. Có thể có hai cây cầu khác nhau nối cùng một cặp đảo.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: tổng quãng đường đi bộ lớn nhất có thể đạt được.

Kết quả của một số bộ kiểm thử không biểu diễn được bằng số nguyên \(32\) bit. Để xử lý đầy đủ các trường hợp, có thể cần dùng int64 trong Pascal hoặc long long trong C/C++. Các giá trị đọc từ đầu vào đều nằm trong phạm vi số nguyên \(32\) bit.

Ràng buộc

• \(2 \le N \le 1\,000\,000\).
• \(1 \le L_i \le 100\,000\,000\) với mọi \(1 \le i \le N\).
• Đảo ở đầu cầu còn lại có số hiệu trong đoạn \([1,N]\) và khác \(i\).

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Mỗi nhóm có trọng số 1. Có 19 nhóm tính điểm; điểm cuối cùng bằng \(100 \times W / 19\), với \(W\) là tổng trọng số các nhóm đạt. Mỗi nhóm đạt đóng góp chính xác \(100/19\) điểm; không làm tròn riêng từng nhóm.

Các ví dụ trong đề không tính điểm. Các tệp ví dụ gốc có nhãn 0 được giữ lại riêng và có trọng số 0.

Tệp ví dụ gốc: isl/isl0.in.

Ví dụ

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

24

Nguồn

IOI 2008.