Balls and Bins

시간 제한1초메모리 제한256 MB

요약
각 bin의 현재 공 개수와 최대 용량이 주어질 때, 가득 찬 bin에서만 이동을 시작할 수 있다는 규칙으로 모든 공을 버릴 수 있는지 판정한다.
난이도

보통10점 중 7점

유형
그리디, 정렬, 구현
정답자
아직 제출이 없습니다

문제

Busy Beaver has NN bins and a large amount of balls. The ii-th bin can hold up to s_is\_i balls and currently contains a_ia\_i balls. In a move, he first chooses a bin ii that is currently full (i.e., a_i=s_ia\_i = s\_i). Then, for each ball in the chosen bin, he chooses to either discard it or move it to a different bin with enough space. (Within the same move, it is allowed to move different balls to different bins.)

Using only these moves, Busy Beaver is trying to remove all of the balls from all of the bins. Determine whether or not it is possible to do so.

입력

Each test contains multiple test cases. The first line of input contains a single integer TT (1≤T≤105)(1\le T\le 10^5), the number of test cases. The description of each test case follows.

The first line of each test case contains a single positive integer NN (1≤N≤5⋅105)(1\le N\le 5\cdot 10^5).

The second line contains NN integers a_1,a_2,…,a_Na\_1,a\_2,\dots, a\_N (1≤a_i≤109)(1\le a\_i\le 10^9) --- the number of balls currently in each bin.

The third line contains NN integers s_1,s_2,…,s_Ns\_1,s\_2,\dots, s\_N (1≤s_i≤109,a_i≤s_i)(1\le s\_i\le 10^9,a\_i\le s\_i) --- the number of balls each bin can hold.

It is guaranteed that the sum of NN across all test cases does not exceed 5⋅1055\cdot 10^5.

출력

For each test case, output "YES" (without quotes) if all bins may be emptied, and "NO" (without quotes) otherwise.

힌트

In the first test case, Busy Beaver can move all the balls in the first bin to the second bin. Then he will have exactly 1+2=31 + 2 = 3 balls in the second bin, making the second bin full.

Then he can move all the balls from the second bin to the third bin. Then he will have exactly 5+3=85 + 3 = 8 balls in the third bin, making the third bin full.

Finally, he can throw all the balls in the third bin away.

In the second test case, it can be shown that it is impossible to discard all the balls.

예제1

  1. 예제 1

    입력
    2
    3
    2 1 5
    2 3 8
    3
    2 3 5
    2 5 11
    
    예상 출력
    YES
    NO