คุณและเพื่อนร่วมทีมอีกสองคนกำลังเข้าร่วมการแข่งขันเขียนโปรแกรม แต่เนื่องจากติดสอบปลายภาค พวกคุณทุกคนจึงต้องกลับก่อนเวลา แต่ละคนมีเวลาที่ต้องเดินทางกลับที่แน่นอน $\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