أنت وزميلاك في الفريق تشاركون في مسابقة برمجة، ولكن بسبب الامتحانات النهائية، يتعين عليكم جميعاً المغادرة مبكراً. لكل واحد منكم وقت مغادرة محدد $\ell_i$ (الوقت بالدقائق بعد بدء المسابقة الذي يجب أن تغادر فيه). بعد المسابقة، تراجعون الحلول وتدركون أن كل مسألة مناسبة تماماً لأحدكم: المسألة $i$ يحلها بأفضل شكل الشخص $p_i$، الذي يمكنه إنجازها في $c_i$ دقيقة دون أي محاولات خاطئة. لسوء الحظ، وبسبب ضغط الامتحانات، لم يكن أداؤكم جيداً في المسابقة الأصلية.
في الحلم، ترى الفريق البطل من البث المباشر: لقد حلوا جميع المسائل الـ $n$ بإجمالي وقت جزاء قدره $t$. وعندما تستيقظ، تكتشف أنك قد بُعثت من جديد في صباح يوم المسابقة. الآن، ومع ذاكرة مثالية لجميع تفاصيل المسائل وأداء الفريق البطل، تريد تحديد ما إذا كانت هناك طريقة لهزيمتهم هذه المرة.
تنص قواعد المسابقة على ما يلي:
- يتوفر جهاز حاسوب واحد فقط، لذا يجب حل المسائل بالتتابع (واحدة تلو الأخرى).
- يجب إسناد كل مسألة $i$ إلى الشخص $p_i$، الذي يجب أن يبدأ في حلها قبل وقت مغادرته $\ell_{p_i}$.
- إذا بدأ الشخص $p_i$ في حل المسألة $i$ عند الوقت $s$، فيجب أن ينتهي منها بحيث يكون $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