Universal Cup Judging System

Universal Cup

حد الوقت: 1 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

أنت وزميلاك في الفريق تشاركون في مسابقة برمجة، ولكن بسبب الامتحانات النهائية، يتعين عليكم جميعاً المغادرة مبكراً. لكل واحد منكم وقت مغادرة محدد $\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.