Cho số nguyên dương \(n\) và dãy số nguyên dương \(a_1,a_2,…,a_n\). Dãy \(a_1,a_2,…,a_n\) được gọi là đẹp nếu không có hai số liên tiếp nào có giá trị bằng nhau, nghĩa là \(a_{i-1}≠a_i\), với \(i=2,…,n.\)

Một phép biến đổi trên dãy \(a\) là chọn một phần tử trên dãy \(a\) và tăng giá trị lên \(1\), nếu tăng phần tử \(a_i\) lên \(1\) thì sẽ mất chi phí \(b_i\). Có thể thực hiện phép biển đổi bao nhiêu lần cũng được và trên bất kỳ phần tử nào, có thể thực hiện phép biến đổi trên một phần tử nhiều lần.

Yêu cầu: Tính chi phí biến đổi ít nhất để dãy \(a_1,a_2,…,a_n\) thành dãy đẹp.

Input

• Dòng thứ nhất chứa số nguyên \(n (1≤n≤3*10^5 ).\)

• Dòng thứ \(i\) trong \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i,b_i (1≤a_i,b_i≤2*10^9 ).\)

Output

• Ghi một số nguyên chi phí biến đổi ít nhất để dãy \(a_1,a_2,…,a_n\) thành dãy đẹp.

Sample Input

3
2 4
2 1
3 5

Sample Output

2