אתה ושני חבריך לצוות משתתפים בתחרות תכנות, אך בשל בחינות הגמר כולכם חייבים לעזוב מוקדם. לכל אחד מכם יש זמן עזיבה מסוים $\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