Ty i twoich dwóch kolegów z drużyny bierzecie udział w zawodach programistycznych, ale z powodu egzaminów końcowych wszyscy musicie wyjść wcześniej. Każdy z was ma określony czas wyjścia $\ell_i$ (czas w minutach od rozpoczęcia zawodów, kiedy musi opuścić salę). Po zawodach analizujecie rozwiązania i zdajecie sobie sprawę, że każde zadanie idealnie pasuje do jednego z was: zadanie $i$ najlepiej rozwiąże osoba $p_i$, która potrafi ukończyć je w $c_i$ minut bez żadnych błędnych zgłoszeń. Niestety, z powodu presji egzaminów, w oryginalnych zawodach nie poszło wam najlepiej.
We śnie widzisz transmisję na żywo z udziałem zwycięskiej drużyny: rozwiązali wszystkie $n$ zadań z łącznym czasem karnym $t$. Gdy się budzisz, odkrywasz, że odrodziłeś się rano w dniu zawodów. Teraz, pamiętając idealnie wszystkie szczegóły zadań oraz wynik mistrzów, chcesz ustalić, czy istnieje sposób, aby tym razem ich pokonać.
Zasady zawodów mówią, że:
- Dostępny jest tylko jeden komputer, więc zadania muszą być rozwiązywane sekwencyjnie (jedno po drugim).
- Każde zadanie $i$ musi zostać przydzielone osobie $p_i$, która musi zacząć je rozwiązywać przed swoim czasem wyjścia $\ell_{p_i}$.
- Jeśli osoba $p_i$ zaczyna rozwiązywać zadanie $i$ w chwili $s$, musi skończyć przed $s + c_i \le \ell_{p_i}$.
- Łączny czas karny to suma czasów ukończenia wszystkich rozwiązanych zadań.
Mając dane $n$, $t$ oraz parametry $p_i$ i $c_i$ dla każdego zadania, rozstrzygnij, czy istnieje taka kolejność rozwiązywania zadań, że:
- Wszystkie $n$ zadań zostaną rozwiązane.
- Łączny czas karny będzie ściśle mniejszy niż $t$.
Jeśli takie ustawienie istnieje, wypisz YES; w przeciwnym razie wypisz NO.
Wejście
Pierwszy wiersz zawiera jedną liczbę całkowitą $q$ ($1 \le q \le 10^5$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:
Pierwszy wiersz zawiera cztery liczby całkowite: $n$, $\ell_1$, $\ell_2$ oraz $\ell_3$ ($1 \le n \le 10^5$, $1 \le \ell_1, \ell_2, \ell_3 \le 3 \cdot 10^7$), oznaczające liczbę zadań oraz czasy wyjścia (w minutach od początku zawodów) trzech członków drużyny.
Każdy z kolejnych $n$ wierszy zawiera dwie liczby całkowite $p_i$ oraz $c_i$ ($1 \le p_i \le 3$, $1 \le c_i \le 300$), gdzie $p_i$ oznacza wyznaczonego członka drużyny dla zadania $i$, a $c_i$ to czas (w minutach) potrzebny mu na jego ukończenie.
Ostatni wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 10^{13}$), oznaczającą łączny czas karny zwycięskiej drużyny.
Suma $n$ po wszystkich przypadkach testowych nie przekracza $10^5$.
Wyjście
Dla każdego przypadku testowego, jeśli istnieje kolejność rozwiązywania zadań spełniająca ograniczenia (wszystkie zadania rozwiązane, czas karny ściśle mniejszy niż $t$), wypisz YES; w przeciwnym razie wypisz NO.
Przykłady
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