Codeforces Round #700 (Div. 2), problem: (B) The Great Hero,

B. The Great Hero
time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
The great hero guards the country where Homer lives. The hero has attack power A and initial health value B. There are n monsters in front of the hero. The i-th monster has attack power ai and initial health value 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); and he or it is said to be dead, if his or its health value is non-positive (less than or equal to 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.

In each fight, the hero can select an arbitrary living monster and fight with it. Suppose the i-th monster is selected, and the health values of the hero and the i-th monster are x and y before the fight, respectively. After the fight, the health values of the hero and the i-th monster become x?ai and y?A, respectively.
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 (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 (1≤A≤109), B (1≤B≤109) and n (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 integers a1,a2,…,an (1≤ai≤109), where ai denotes the attack power of the i-th monster.

The third line of each test case contains n integers b1,b2,…,bn (1≤bi≤109), where bi denotes the initial health value of the i-th monster.

It is guaranteed that the sum of n over all test cases does not exceed 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).

Example
inputCopy
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
outputCopy
YES
YES
YES
NO
YES
Note
In the first example: There will be 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. 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, 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-st, 2-nd, 3-rd and 4-th monsters. After all fights, the health value of the hero becomes ?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. So the answer is “NO”.
題解：本題雖然說的是可以任意選擇怪獸進行攻擊，同時也存在著一個坑點----------如果最后一只怪獸的攻擊力特別大的話并且兩者同歸于盡，那么此時就會成功守衛王國；反之，如果將這種攻擊力較強的放在前面的話，則不會守護王國，這樣的求解與答案本身是矛盾的，只需進行對于怪獸的攻擊力進行求最大值即可，另外一個需要注意的是當怪獸的生命力如果不能整除英雄的攻擊力的話，則需要整除后+1操作

#include<bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
struct {
	long long a;//怪物的攻擊
	long long b;//怪物的生命力
	long long c;//能承受英雄的多少次攻擊
}d[100005];
int main()
{
    FAST;
    int t;
    cin>>t;
    while(t--)
    {
    	long long A,B,n;
    	cin>>A>>B>>n;
   // memset(d,0,sizeof(d));容易超時
    long long mm=0;
	for(long long i=1;i<=n;i++)
	{
		cin>>d[i].a;
		mm=std::max(mm,d[i].a);
	 } 
	 for(long long i=1;i<=n;i++)
	 {
	 	cin>>d[i].b;
	 	if(d[i].b%A!=0)
              d[i].c=d[i].b/A+1;
        else
              d[i].c=d[i].b/A;
	 }
	 for(long long i=1;i<=n;i++)
	 {
	 	B-=d[i].c*d[i].a;
	 }
		if(B+mm<=0)//如果能達到倒數第二次的攻擊時，判斷此時英雄的生命之值
		  cout<<"NO"<<endl;
		else
		cout<<"YES"<<endl;
    } 
   //system("pause");
}