Đức vừa tốt nghiệp đại học loại xuất sắc ngành Công nghệ thông tin tại một trường đại học danh tiếng. Đức đã tìm hiểu, lên kế hoạch khởi nghiệp từ thời đang là sinh viên và nay là thời điểm mà Đức thực hiện kế hoạch đó. Qua tìm hiểu, Đức biết được \(N\) công ty tiềm năng và có liên quan đến công việc của mình nên sẽ hợp tác với \(N\) công ty này. Các công ty được đánh số thứ tự \(1, 2, \ldots, N\). Điều kiện để hợp tác với công ty thứ \(i\) (\(i = 1, 2, \ldots, N\)) là: Đức đã hợp tác được với ít nhất \(a_i\) công ty khác (trong \(N-1\) công ty còn lại) hoặc là mua một món quà có giá trị \(b_i\) (đồng) để tặng cho công ty thứ \(i\).

Ban đầu, Đức chưa hợp tác được với công ty nào. Hãy tính chi phí ít nhất để Đức có thể hợp tác được với \(N\) công ty.

Input

• Dòng 1 ghi số nguyên dương \(N\) là số lượng công ty;
• \(N\) dòng tiếp theo, dòng thứ \(i\) ghi hai số nguyên \(a_i\), \(b_i\) (\(1 \leq i \leq N\), \(a_i \leq N\), \(0 \leq b_i \leq 10^4\)).

Output

• Ghi ra một số nguyên duy nhất là chi phí thấp nhất để Đức có thể hợp tác với tất cả \(N\) công ty.

Example

4
3 6
1 2
0 5
3 7

6

Scoring

• Subtask 1: có 10 test (\(25\%\)), tương ứng 1,0 điểm với \(1 \leq N \leq 20\);
• Subtask 2: có 10 test (\(25\%\)), tương ứng 1,0 điểm với \(20 < N \leq 2 \times 10^5\), \(a_1 = a_2 = \ldots = a_N\);
• Subtask 3: có 10 test (\(25\%\)), tương ứng 1,0 điểm với \(20 < N \leq 2 \times 10^5\), \(b_1 = b_2 = \ldots = b_N\);
• Subtask 4: có 10 test (\(25\%\)), tương ứng 1,0 điểm với \(20 < N \leq 2 \times 10^5\).