Universal Cup Judging System

Universal Cup

Límite de tiempo: 1 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.