作为一名忙碌的商人，约翰知道必须高效地安排他的时间。他有 N(1≤N≤1000) 个工作要做，比如给奶牛挤奶，清洗牛棚，修理栅栏之类的。

为了高效，约翰列出了所有工作的清单。第 i(1≤i≤N) 个工作需要 Ti​(1≤Ti​≤1000) 单位的时间来完成，而且必须在 1≤Si​≤106 或之前完成。现在是 0 时刻。约翰做一份工作必须直到做完才能停止。

所有的商人都喜欢睡懒觉。请帮约翰计算他最迟什么时候开始工作，可以让所有工作按时完成。（如果始终无法完成全部任务，输出 -1）

输入格式

第一行，一个整数 N

接下来 N 行，每行 2 个有空格分隔的整数 Ti​,Si​

输出格式

一行，一个整数，表示约翰可以开始工作的最晚时间，如果约翰无法完成所有工作，则为 -1

输入输出样例

输入 #1

4 
3 5 
8 14 
5 20 
1 16 

输出 #1

2 

说明/提示

【样例解释】

约翰有 4 个工作要做，分别需要 3、8、5 和 1 个时间单位，并且必须分别在时间 5、14、20 和 16 之前完成。

约翰必须在时间 2 开始第一个作业。然后他可以按此顺序完成第二、第四和第三项工作，以按时完成。

【代码示例】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n;

struct task {
	int t;
	int s;
} T[MAXN];

bool cmp(task a, task b) {
	return a.s < b.s;
}

bool check(int x) {
	int sum = x;
	for (int i = 1; i <= n; i++) {
		sum += T[i].t;
		if (sum > T[i].s) {
			return false;
		}
	}
	return true;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> T[i].t >> T[i].s;
	}
	sort(T + 1, T + n + 1, cmp);
	int l = 0, r = 1e6, ans = -1;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (check(mid)) {
			l = mid + 1;
			ans = mid;
		} else {
			r = mid - 1;
		}
	}
	cout << ans;
}