import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;

public class most {

    /**
     * @param args the command line arguments
     */
    /*
    public static void main(String[] args) throws Exception {
    doMain(System.in);
    }d
     *
     */
    public static void main(String[] args) throws Exception {
        //doMain(new FileInputStream(new File("testData")));
        doMain(System.in);
    }

    private static void doMain(InputStream is) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(is));
        String line;
        reader.readLine();
        while ((line = reader.readLine()) != null) {
            int height = Integer.parseInt(line);
            List<List<Integer>> data = new ArrayList<List<Integer>>(height);
            for (int i = 0; i < height; i++) {
                line = reader.readLine();
                List<Integer> ints = readLine(line);
                data.add(ints);
            }
            doMostInstance(data);
        }
        reader.close();
    }

    private static List<Integer> readLine(String s) {
        String[] arr = s.split(" ");

        List<Integer> list = new ArrayList<Integer>();
        for (String a : arr) {
            if (!a.isEmpty()) {
                list.add(Integer.parseInt(a));
            }
        }

        return list;
    }

    private static void testPrint(Collection<? extends Object> s) {
        for (Object any : s) {
            System.out.println(any);
        }
    }

    /*
    private static void doMost(List<List<Integer>> data) {
    int line = 0;
    int instanceCount = data.get(line++).get(0);
    
    for (int i = 0; i < instanceCount; i++) {
    int instanceHeight = data.get(line++).get(0);
    List<List<Integer>> instanceData = data.subList(line, line + instanceHeight);
    line = line + instanceHeight;
    
    doMostInstance(instanceData);
    }
    }
     * */
    private static void doMostInstance(List<List<Integer>> data) {
        int instanceMin = Integer.MAX_VALUE;

        Min min = new Min();
        for (List<Integer> pair : data) {
            min.min(pair.get(1) - pair.get(0));
        }

        int num = 0;
        outer:
        for (List<Integer> pair : data) {
            
            int since = Math.max(0, num - min.getMin());
            int until = Math.min(data.size() , (num + min.getMin()));
            
            
            for (int i = since; i < until; i++) {
            
                int diffBanks = (data.get(i).get(1) - pair.get(0));
                int diffRows = Math.abs(i);
//                System.out.println("---" + data.get(i).get(1) +"---" + pair.get(0) +"---" + diffBanks);
                if (diffBanks <= 0){
                    min.min(diffRows - 1);
                } else {
                    min.min(diffBanks + diffRows - 1); //B
                }
                
                if (min.getMin() == 0) {
                    break outer;
                }
            }
            num++;
        }

        System.out.println("K prechodu reky je treba " + min.getMin() + " pontonu.");
    }

    private static class Min {

        int instanceMin = Integer.MAX_VALUE;

        private int min(int a) {
            instanceMin = Math.min(a, instanceMin);
            return instanceMin;
        }

        private int getMin() {
            return instanceMin;
        }
    }
}