Codeforces Round #700 (Div. 2)-B. The Great Hero

傳送門
Time Limit: 2 seconds
Memory Limit: 512 megabytes

Problem Description

The great hero guards the country where Homer lives. The hero has attack power A A A and initial health value B B B. There are n n n monsters in front of the hero. The i i i-th monster has attack power a i a_i ai? and initial health value b i b_i bi?.

The hero or a monster is said to be living, if his or its health value is positive (greater than or equal to 1 1 1); and he or it is said to be dead, if his or its health value is non-positive (less than or equal to 0 0 0).

In order to protect people in the country, the hero will fight with monsters until either the hero is dead or all the monsters are dead.**Note that the hero can fight the same monster more than once.**For the safety of the people in the country, please tell them whether the great hero can kill all the monsters (even if the great hero himself is dead after killing the last monster).

Input

Each test contains multiple test cases. The first line contains t t t ( 1 ≤ t ≤ 1 0 5 1 \le t \le 10^5 1≤t≤105) — the number of test cases. Description of the test cases follows.

The first line of each test case contains three integers A A A ( 1 ≤ A ≤ 1 0 9 1 \leq A \leq 10^9 1≤A≤109), B B B ( 1 ≤ B ≤ 1 0 9 1 \leq B \leq 10^9 1≤B≤109) and n n n ( 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105) — the attack power of the great hero, the initial health value of the great hero, and the number of monsters.

The second line of each test case contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1?,a2?,…,an? ( 1 ≤ a i ≤ 1 0 9 1 \leq a_i \leq 10^9 1≤ai?≤109), where a i a_i ai? denotes the attack power of the i i i-th monster.

The third line of each test case contains n n n integers b 1 , b 2 , … , b n b_1, b_2, \dots, b_n b1?,b2?,…,bn? ( 1 ≤ b i ≤ 1 0 9 1 \leq b_i \leq 10^9 1≤bi?≤109), where b i b_i bi? denotes the initial health value of the i i i-th monster.

It is guaranteed that the sum of n n n over all test cases does not exceed 1 0 5 10^5 105.

Output

For each test case print the answer: “YES” (without quotes) if the great hero can kill all the monsters. Otherwise, print “NO” (without quotes).

Sample Input

5
3 17 1
2
16
10 999 3
10 20 30
100 50 30
1000 1000 4
200 300 400 500
1000 1000 1000 1000
999 999 1
1000
1000
999 999 1
1000000000
999

Sample Onput

YES
YES
YES
NO
YES

Note

In the first example: There will be 6 6 6 fights between the hero and the only monster. After that, the monster is dead and the health value of the hero becomes 17 ? 6 × 2 = 5 > 0 17 - 6 \times 2 = 5 > 0 17?6×2=5>0. So the answer is “YES”, and moreover, the hero is still living.

In the second example: After all monsters are dead, the health value of the hero will become 709 709 709, regardless of the order of all fights. So the answer is “YES”.

In the third example: A possible order is to fight with the 1 1 1-st, 2 2 2-nd, 3 3 3-rd and 4 4 4-th monsters. After all fights, the health value of the hero becomes ? 400 -400 ?400. Unfortunately, the hero is dead, but all monsters are also dead. So the answer is “YES”.

In the fourth example: The hero becomes dead but the monster is still living with health value 1000 ? 999 = 1 1000 - 999 = 1 1000?999=1. So the answer is “NO”.

題目大意

英雄 A A A攻擊 B B B滴血
小怪 i i i有 a i a_i ai?的攻擊和 b i b_i bi?的血
每次英雄有選擇的單挑，問英雄能不能殺死所有的怪

注意事項

問的是能不能殺死所有的怪，沒有說英雄一定要活著，最后可能同歸于盡

傷害是1e9級別，多個傷害疊加可能超過int范圍（我這這里錯了好多次）

解題思路

最后殺哪個怪？
當然是最后殺攻擊最高的怪，
因為殺了這個怪可能就同歸了，如果先殺攻擊高的怪，可能其他小怪還沒殺就和這個大怪同歸了，

最后一刀給攻擊最高的怪，如何計算最后一刀之前英雄血量的狀態呢？
相當于先打敗所有怪，再把最后一刀掉的血加上（加上一個最高傷害）

最后一刀之前，只有英雄還活著，它就能殺出這最后一刀，即為殺死所有的小怪，

哪怕中途英雄已經死了，也不影響最終的判斷，

AC代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct gs //怪獸
{
	ll a, b; //a是血量,b是傷害（攻擊）
} mon[100010];
int main()
{
	ll N;
	cin >> N;
	while (N--)
	{
		ll A, B, n;
		scanf("%lld%lld%lld", &A, &B, &n); //英雄血量、英雄傷害、小怪數量
		ll Msh = 0;						   // 來記錄小怪的最大傷害
		for (ll i = 0; i < n; i++)
		{
			scanf("%lld", &mon[i].a);
			Msh = max(Msh, mon[i].a); //更新小怪的最大傷害
		}
		for (ll i = 0; i < n; i++)
		{
			scanf("%lld", &mon[i].b);
		}
		for (ll i = 0; i < n; i++)
		{
			//times是需要攻擊這個小怪的次數
			ll times = mon[i].b / A + (mon[i].b % A != 0);
			/*times
				首先times=mon[i].b/A是向下取整
				接下來如果(mon[i].b % A != 0)，則括號里為true（1），正好為向上取整
			*/
			B -= times * mon[i].a; //減去英雄受到的傷害
		}
		B += Msh; //恢復到最后一刀之前的狀態
		puts(B <= 0 ? "NO" : "YES"); //英雄血量B  小于0嗎？  如果是,puts("NO")   否則,puts("YES")
	}
	return 0;
}