D. SCUT Classroom Relocation
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

South China University of Technology (SCUT) has $$$m$$$ classrooms available for self-study. The $$$j$$$-th classroom currently has $$$c_j$$$ spare seats.

There are $$$n$$$ study groups on campus. The $$$i$$$-th study group consists of $$$q_i$$$ students and is initially assigned to their primary classroom $$$p_i$$$.

Due to a sudden campus-wide air conditioning maintenance drill, all study groups must be evacuated from their primary classrooms. Specifically, each student from the $$$i$$$-th study group must be relocated to any classroom $$$j$$$ such that $$$j \neq p_i$$$. Students from the same group can be split and sent to different classrooms. Multiple students from various groups can be assigned to the same classroom, provided that the total number of newly added students does not exceed the classroom's spare capacity $$$c_j$$$.

Given the capacities of the classrooms and the sizes of the study groups, determine if it is possible to successfully relocate all students without exceeding the spare capacity of any classroom.

Input

The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^6$$$) — the number of study groups and the number of classrooms, respectively.

The second line of each test case contains $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_j \le 10^9$$$) — the spare capacities of the classrooms.

The following $$$n$$$ lines describe the study groups. The $$$i$$$-th of these lines contains two integers $$$q_i$$$ and $$$p_i$$$ ($$$1 \le q_i \le 10^9$$$, $$$1 \le p_i \le m$$$) — the number of students in the $$$i$$$-th group and the index of their primary classroom.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$10^6$$$.

Output

For each test case, print the answer on a new line — YES if it is possible to successfully relocate all students, and NO otherwise.

Example
Input
4
1 1
10
1 1
2 3
2 2 2
4 1
3 2
3 3
5 3 4
5 1
3 1
1 2
2 2
3 3
3 1
3 2
Output
NO
NO
NO
YES