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.