作为一名忙碌的商人，约翰知道必须高效地安排他的时间。他有 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;
}

当你正在散步时，突然出现了 N 只魔物。每只魔物拥有一个称为体力的数值，第 i 只魔物出现时的体力为 hi​。当某只魔物的体力降至 0 以下时，它会立刻消失。

幸运的是，你是一名熟练的魔法师，能够使用爆炸攻击魔物。每次爆炸时，你可以按以下方式减少魔物的体力：

• 选择一只仍然存活的魔物，以它为中心引发爆炸。爆炸中心的魔物体力减少 A，其余所有魔物的体力各自减少 B。其中 A 和 B 是已知的常数，且 A>B。

要彻底消灭所有魔物，最少需要引发多少次爆炸？

输入格式

输入以如下格式给出。

N A B h1​ h2​ … hN​

输出格式

输出消灭所有魔物所需的最小爆炸次数。

输入输出样例

输入 #1

4 5 3
8
7
4
2

输出 #1

2

输入 #2

2 10 4
20
20

输出 #2

4

输入 #3

5 2 1
900000000
900000000
1000000000
1000000000
1000000000

输出 #3

800000000

说明/提示

限制

• 输入中的所有数均为整数。
• 1≤N≤105
• 1≤B<A≤109
• 1≤hi​≤109

样例解释 1

可以通过以下方式，在 2 次爆炸内消灭全部魔物：

• 首先，以体力为 8 的魔物为中心引爆。四只魔物的体力分别变为 3，4，1，−1，最后一只魔物消失。
• 接着，再以剩余体力为 4 的魔物为中心引爆。剩下的三只魔物体力分别变为 0，−1，−2，于是全部消失。

样例解释 2

必须分别以每只魔物为中心进行 2 次爆炸，总共需要 4 次爆炸。

【代码示例】

#include <bits/stdc++.h>
using namespace std;
int n, a, b, h[100005];

bool cmp(int x, int y) {
	return x > y;
}

int ceil(int x, int y) {
	if (x % y == 0)
		return x / y;
	else
		return x / y + 1;
}//向上取整

bool check(long long x) {
	long long cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (h[i] <= x * b)
			continue;
		//若x次伤害为B的爆炸可以把他消灭把它消灭
		cnt += ceil(h[i] - x * b, a - b);
		//用伤害为A的爆炸将他消灭
	}
	return cnt <= x;
}

int main() {
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++)
		cin >> h[i];

	long long  l = 0, r = 1e18, ans = -1;
	while (l <= r) {
		long long mid = l + (r - l) / 2;
		if (check(mid)) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << ans;
}