G. Void and Moon's Brainrot
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Moon has $$$S$$$ minutes remaining before his flight and wants to sleep for at least $$$x$$$ minutes.

His friend Void sends him $$$n$$$ reels, where the $$$i$$$-th reel takes $$$s_i$$$ minutes to watch. Moon must first watch all $$$n$$$ reels, and then reply to each one with a reel of the exact same duration.

To find these replies, Moon opens his own feed containing $$$m$$$ reels, where the $$$j$$$-th reel takes $$$b_j$$$ minutes to watch. He follows this exact process:

  • He watches the reels in his feed sequentially, starting from $$$j = 1$$$ without skipping any;
  • If the current reel $$$b_j$$$ matches the duration of an unanswered reel from Void, he pairs them up. (If Void sent multiple reels of the same duration, Moon must find a distinct matching reel for each one).
  • He stops watching his feed the exact moment he successfully finds a match for all $$$n$$$ of Void's reels.

Determine if Moon's feed contains all $$$n$$$ necessary replies AND if his total time spent watching reels (both Void's and his own) leaves him with at least $$$x$$$ minutes remaining to sleep.

Input

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

The first line of each test case contains four integers $$$n$$$, $$$m$$$, $$$x$$$, and $$$S$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \le x \le S \le 10^{14}$$$) — the number of reels Void sent, the number of reels on Moon's feed, the required minutes of sleep, and the total minutes remaining until the flight.

The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) — the duration of each reel sent by Void, in minutes.

The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^9$$$) — the duration of each reel on Moon's feed, in minutes.

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

Output

For each testcase print "YES" (without quotes) if Moon can successfully find all matching reels and have at least $$$x$$$ minutes remaining to sleep.

Otherwise, print "NO". This includes situations where Moon does not have enough time, as well as situations where it is impossible to find all required matching reels in his feed.

the "YES"s and "NO"s are case-insensitive, meaning that outputs such as "yEs" and "nO" are valid. However, the grid is case-sensitive.

Example
Input
5
3 5 60 100
5 2 5
1 5 2 3 5
1 3 10 20
10
1 2 3
2 3 60 70
5 5
5 5 5
1 1 30 40
5
5
2 4 10 100
3 3
3 1 2 4
Output
YES
NO
NO
YES
NO