Великий герой охраняет страну, где живет Гомер. У героя есть сила атаки A и начальное количество здоровья B. Перед героем стоят n монстров. i-й монстр имеет силу атаки ai и начальное количество здоровья bi.
Герой или монстр жив, если его здоровье положительно (больше или равно 1); и мертв, если его здоровье не положительно (меньше или равно 0).
Чтобы защитить людей в стране, герой будет сражаться с монстрами до тех пор, пока либо герой не умрет, либо все монстры не умрут.
Заметьте, что герой может сражаться с одним и тем же монстром несколько раз.
Для безопасности людей в стране, пожалуйста, скажите им, может ли великий герой убить всех монстров (даже если великий герой сам умрет после убийства последнего монстра).
Каждый тест содержит несколько наборов входных данных. Первая строка содержит t (1≤t≤105) — количество наборов входных данных. Описание наборов входных данных приведено ниже.
Первая строка каждого набора входных данных содержит три целых числа A (1≤A≤106), B (1≤B≤106) и n (1≤n≤105) — силу атаки великого героя, начальное количество здоровья великого героя и количество монстров соответственно.
Вторая строка каждого набора входных данных содержит n целых чисел a1,a2,…,an (1≤ai≤106), где ai обозначает силу атаки i-го монстра.
Третья строка каждого набора входных данных содержит n целых чисел b1,b2,…,bn (1≤bi≤106), где bi обозначает начальное значение здоровья i-го монстра.
Гарантируется, что сумма n по всех наборах входных данных не превышает 105.
Для каждого набора входных данных выведите ответ «YES» (без кавычек), если великий герой может убить всех монстров, в противном случае выведите «NO» (без кавычек).
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 1000000 999
YES YES YES NO YES
В первом наборе входных данных будет 6 боев между героем и единственным монстром. После этого монстр умирает, а количество здоровья героя становится 17−6×2=5>0. Поэтому ответ: «YES», а кроме того, герой все еще жив.
Во втором наборе входных данных после того, как все монстры мертвы, значение здоровья героя станет 709 независимо от порядка всех боев. Таким образом, ответ «YES».
В третьем наборе входных данных возможный порядок — сражаться с 1-м, 2-м, 3-м и 4-м монстрами в этом порядке. После всех поединков количество здоровья героя становится −400. К сожалению, герой мертв, но все монстры тоже мертвы. Так что ответ: «YES».
В четвертом наборе входных данных герой умирает, но монстр остается живым с количеством здоровья, равным 1000−999=1. Таким образом, ответ «NO».
| Codeforces Round 700 (Div. 2) |
|---|
| Закончено |
