There are n cities numbered from 1 to n, and city i has beauty a_i.

A salesman wants to start at city 1, visit every city exactly once, and return to city 1.

For all i≠ j, a flight from city i to city j costs max(c_i,a_j-a_i) dollars, where c_i is the price floor enforced by city i. Note that there is no absolute value. Find the minimum total cost for the salesman to complete his trip.

Input

The first line contains a single integer n (2≤ n≤ 10^5) — the number of cities.

The i-th of the next n lines contains two integers a_i, c_i (0≤ a_i,c_i≤ 10^9) — the beauty and price floor of the i-th city.

Output

Output a single integer — the minimum total cost.

Examples

Input


3
1 9
2 1
4 1


Output


11


Input


6
4 2
8 4
3 0
2 3
7 1
0 1


Output


13

Note

In the first test case, we can travel in order 1→ 3→ 2→ 1. 

  * The flight 1→ 3 costs max(c_1,a_3-a_1)=max(9,4-1)=9. 
  * The flight 3→ 2 costs max(c_3, a_2-a_3)=max(1,2-4)=1. 
  * The flight 2→ 1 costs max(c_2,a_1-a_2)=max(1,1-2)=1. 



The total cost is 11, and we cannot do better.
import java.util.*;
import java.io.*;

public class C1503 {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int n = sc.nextInt();
		SegmentTree sg1 = new SegmentTree(n);
		SegmentTree sg2 = new SegmentTree(n);
		Pair[] arr = new Pair[n];
		for (int i = 0; i < n; i++) {
			arr[i] = new Pair(sc.nextInt(), sc.nextInt());
		}
		Arrays.sort(arr, (u, v) -> Long.compare(u.a, v.a));
		long[] c = new long[n];
		c[0] = arr[0].c;
		for (int i = 1; i < n; i++) {
			c[i] = c[i - 1] + arr[i].c;
		}
		long[] dp = new long[n];
		dp[n - 1] = arr[n - 1].c;
		sg1.update_point(n - 1, c[n - 1] + arr[n - 1].a);
		sg2.update_point(n - 1, c[n - 1]);
		for (int i = n - 2; i >= 0; i--) {
			int lo = i + 1;
			int hi = n - 1;
			int ans = n;
			while (lo <= hi) {
				int mid = lo + hi >> 1;
				if (arr[mid].a > arr[i].a + arr[i].c) {
					ans = mid;
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			}
			dp[i] = sg1.query(ans, n - 1) - c[i] - arr[i].a;
			dp[i] = Math.min(dp[i], sg2.query(i + 1, ans - 1) - c[i] + arr[i].c);
			if (i != 0) {
				sg1.update_point(i, dp[i] + c[i - 1] + arr[i].a);
				sg2.update_point(i, dp[i] + c[i - 1]);
			}
//			pw.println(Arrays.toString(sg1.sTree));
//			pw.println(c[i] + " " + arr[i].a);
//			pw.println(Arrays.toString(sg2.sTree));
//			pw.println(c[i] + " " + arr[i].c);
		}
//		pw.println(Arrays.toString(dp));
		pw.println(dp[0]);
		pw.close();
	}

	static class Pair {
		long a, c;

		public Pair(int a, int c) {
			this.a = a;
			this.c = c;
		}
	}

	static class SegmentTree { // 1-based DS, OOP

		int N; // the number of elements in the array as a power of 2 (i.e. after padding)
		long[] sTree;

		SegmentTree(int n) {
			N = 1;
			while (N <= n) {
				N <<= 1;
			}
			sTree = new long[N << 1]; // no. of nodes = 2*N - 1, we add one to cross out index zero
			Arrays.fill(sTree, (long) 1e18);
		}

		void update_point(int index, long val) // O(log n)
		{
			index += N;
			sTree[index] = val;
			while (index > 1) {
				index >>= 1;
				sTree[index] = Math.min(sTree[index << 1], sTree[index << 1 | 1]);
			}
		}

		long query(int i, int j) {
			if (i > j) {
				return (long) 1e18;
			}
			return query(1, 1, N, i + 1, j + 1);
		}

		long query(int node, int b, int e, int i, int j) // O(log n)
		{
			if (i > e || j < b)
				return (long) 1e18;
			if (b >= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
			long q1 = query(node << 1, b, mid, i, j);
			long q2 = query(node << 1 | 1, mid + 1, e, i, j);
			return Math.min(q1, q2);

		}
	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader f) {
			br = new BufferedReader(f);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArr(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(next());
			}
			return arr;
		}

	}

}
