你同你嘅兩名隊友參加緊一場編程比賽,但係因為期末考,你哋全部人都必須提早離開。你哋每個人都有一個特定嘅離開時間 $\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