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.io.*;
import java.util.*;

public class Main{
	static void main() throws Exception{
		int n=sc.nextInt();
		int[][]in=new int[n][];
		long sum=0;
		
		for(int i=0;i<n;i++) {
			in[i]=new int[] {sc.nextInt(),sc.nextInt(),i,0};
			in[i][3]=in[i][0]+in[i][1];
			sum+=in[i][1];
		}
		Arrays.sort(in,(x,y)->y[0]-x[0]);
		int min=in[n-1][0];
		int bestSum=in[n-1][3];
		for(int i=n-2;i>=0;i--) {
			bestSum=Math.max(bestSum, in[i][3]);
			in[i][3]=bestSum;
		}
		int[]dist=new int[n];
		for(int i=1;i<n;i++) {
			int curD=Math.max(0, in[i-1][0]-in[i][3]);
			dist[in[i][2]]=curD+dist[in[i-1][2]];
		}
		long ans=(long)1e18;
		for(int i=0;i<n;i++) {
			if(in[i][0]==min) {
				ans=Math.min(ans, dist[in[i][2]]);
			}
		}
		pw.println(ans+sum);
    }
    public static void main(String[] args) throws Exception{
    	sc=new MScanner(System.in);
    	pw = new PrintWriter(System.out);
    	
        int tc=1;
//        tc=sc.nextInt();
        for(int i=1;i<=tc;i++) {
//            pw.printf("Case %d:\n", i);
            main();
        }
        pw.flush();
    }
    static PrintWriter pw;
    static MScanner sc;
    static class MScanner {
        StringTokenizer st;
        BufferedReader br;
        public MScanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }
     
        public MScanner(String file) throws Exception {
            br = new BufferedReader(new FileReader(file));
        }
     
        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        public int[] intArr(int n) throws IOException {
            int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
            return in;
        }
        public long[] longArr(int n) throws IOException {
            long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            return in;
        }
        public int[] intSortedArr(int n) throws IOException {
            int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
            shuffle(in);
            Arrays.sort(in);
            return in;
        }
        public long[] longSortedArr(int n) throws IOException {
            long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            shuffle(in);
            Arrays.sort(in);
            return in;
        }
        public Integer[] IntegerArr(int n) throws IOException {
            Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
            return in;
        }
        public Long[] LongArr(int n) throws IOException {
            Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            return in;
        }
        public String nextLine() throws IOException {
            return br.readLine();
        }
     
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
     
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
     
        public char nextChar() throws IOException {
            return next().charAt(0);
        }
     
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
     
        public boolean ready() throws IOException {
            return br.ready();
        }
     
        public void waitForInput() throws InterruptedException {
            Thread.sleep(100);
        }
        
    }
    static void shuffle(int[]in) {
        for(int i=0;i<in.length;i++) {
            int idx=(int)(Math.random()*in.length);
            int tmp=in[i];
            in[i]=in[idx];
            in[idx]=tmp;
        }
    }
    static void shuffle(long[]in) {
        for(int i=0;i<in.length;i++) {
            int idx=(int)(Math.random()*in.length);
            long tmp=in[i];
            in[i]=in[idx];
            in[idx]=tmp;
        }
    }
}