你和你的兩名隊友正在參加一場程式設計比賽,但由於期末考,你們都必須提前離開。你們每個人都有一個特定的離開時間 $\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。
範例
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
YES
NO
1
1 100 300 300
1 300
300
NO