你和你的两名队友正在参加一场编程比赛，但由于期末考试，你们都必须提前离开。你们每个人都有一个特定的离开时间 $\ell_i$（比赛开始后你必须离开的分钟数）。赛后，你们复盘了题解，并意识到每道题都完美适合你们中的某一个人：第 $i$ 题最适合由人员 $p_i$ 来解决，他可以在 $c_i$ 分钟内完成，且不会有任何错误提交。不幸的是，由于考试的压力，你们在原本的比赛中表现不佳。

在梦中，你看到了冠军队伍的直播：他们解决了所有 $n$ 道题，总罚时为 $t$。当你醒来时，你发现自己重生到了比赛当天的早上。现在，凭借对所有题目细节和冠军表现的完美记忆，你想确定这次是否有办法击败他们。

比赛规则如下：

• 只有一台电脑可用，因此题目必须按顺序依次解决（一道接一道）。
• 每道题 $i$ 必须分配给人员 $p_i$，且他必须在其离开时间 $\ell_{p_i}$ 之前开始解答。
• 如果人员 $p_i$ 在时间 $s$ 开始解答第 $i$ 题，他必须在 $s + c_i \le \ell_{p_i}$ 之前完成。
• 总罚时是所有已解决题目的完成时间之和。

给定 $n$、$t$ 以及每道题的参数 $p_i$ 和 $c_i$，请判断是否存在一种做题顺序，使得：

• 所有 $n$ 道题都被解决。
• 总罚时严格小于 $t$。

如果存在这样的安排，输出 YES；否则，输出 NO。

输入格式

第一行包含一个整数 $q$ ($1 \le q \le 10^5$)，表示测试用例的数量。对于每个测试用例：

第一行包含四个整数：$n$、$\ell_1$、$\ell_2$ 和 $\ell_3$ ($1 \le n \le 10^5$, $1 \le \ell_1, \ell_2, \ell_3 \le 3 \cdot 10^7$)，分别表示题目的数量以及三名队友的离开时间（比赛开始后的分钟数）。

接下来的 $n$ 行，每行包含两个整数 $p_i$ 和 $c_i$ ($1 \le p_i \le 3$, $1 \le c_i \le 300$)，其中 $p_i$ 表示第 $i$ 题的指定队友，$c_i$ 表示他完成该题所需的时间（分钟）。

最后一行包含一个整数 $t$ ($1 \le t \le 10^{13}$)，表示冠军队伍的总罚时。

所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，如果存在满足限制条件的做题顺序（所有题目都被解决，且总罚时严格小于 $t$），输出 YES；否则，输出 NO。

样例

输入样例 1

2
3 100 150 175
1 100
2 25
3 50
401
5 100 200 300
1 30
1 30
1 40
2 110
3 50
1275

输出样例 1

YES
NO

输入样例 2

1
1 100 300 300
1 300
300

输出样例 2

NO