当前没有测试数据。

题目描述

小 $A$ 是一位艺术展策划人，负责筹备即将在当地美术馆开幕的大型艺术展。为了成功举办此次展览，她需要完成 $N$ 项准备工作，如安排艺术品的运输、布展以及广告宣传等。

每项工作都有其特定的截止时间和完成所需的时间。小 $A$ 希望尽可能晚地开始工作，以便能多花时间与艺术家交流并精细调整展览布局。现在，她希望你帮助她计算最晚开始工作的时间，以便所有工作都能按时完成。

如果无论如何都无法完成所有任务，输出 $-1$。

输入格式

第一行，读入一个整数 $N$，表示需要完成的工作数量。

接下来 $N$ 行，每行包含两个整数，第一个整数表示完成该项工作所需的连续时间 $T_i$，第二个整数表示该项工作的截止时间 $E_i$。

请注意： 小 $A$ 最早可以从 $0$ 时刻开始工作，最晚可以工作到 $10^6$ 时刻，他做每项工作都需要连续的时间，在前一项工作完成之后，才能开始下一项工作。

你可以通过样例解释，进一步的明确变量的含义。

输出格式

输出一个整数，表示小 $A$ 可以最晚开始工作的时间。如果无法按时完成所有工作，则输出 $-1$。

样例

输入

4
2 6
6 16
4 20
1 18

输出

4

输入

10
12 85
6 61
7 99
1 63
3 81
3 85
5 71
7 36
8 69
4 84

输出

29

输入

4
1 8
8 10
2 6
3 15

输出

-1

数据范围

对于 $30\%$ 的测试数据，满足 $1 \le N \le 100$。

对于 $100\%$ 的测试数据，满足 $1 \le N \le 1000$，$1 \le T_i \le 1000$，$1 \le E_i \le 10^6$。