Universal Cup Judging System

Universal Cup

时间限制: 1 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

Bạn và hai đồng đội của mình đang tham gia một kỳ thi lập trình, nhưng do kỳ thi cuối kỳ nên tất cả các bạn đều phải rời đi sớm. Mỗi người trong các bạn có một thời điểm rời đi cụ thể $\ell_i$ (thời gian tính bằng phút sau khi kỳ thi bắt đầu mà bạn phải rời đi). Sau kỳ thi, các bạn xem lại lời giải và nhận ra rằng mỗi bài toán đều hoàn toàn phù hợp với một người trong nhóm: bài toán $i$ được giải tốt nhất bởi người $p_i$, người có thể hoàn thành nó trong $c_i$ phút mà không có bất kỳ lần nộp sai nào. Thật không may, do áp lực thi cử, các bạn đã không thể hiện tốt trong kỳ thi ban đầu.

Trong một giấc mơ, bạn nhìn thấy đội vô địch từ buổi phát sóng trực tiếp: họ đã giải được tất cả $n$ bài toán với tổng thời gian phạt là $t$. Khi tỉnh dậy, bạn phát hiện ra mình đã được tái sinh vào buổi sáng ngày diễn ra kỳ thi. Giờ đây, với trí nhớ hoàn hảo về mọi chi tiết của các bài toán và thành tích của nhà vô địch, bạn muốn xác định xem liệu có cách nào để đánh bại họ trong lần này hay không.

Luật thi quy định:

  • Chỉ có một máy tính duy nhất, vì vậy các bài toán phải được giải tuần tự (hết bài này đến bài khác).
  • Mỗi bài toán $i$ phải được giao cho người $p_i$, và người đó phải bắt đầu giải trước thời điểm rời đi $\ell_{p_i}$ của mình.
  • Nếu người $p_i$ bắt đầu giải bài toán $i$ tại thời điểm $s$, họ phải hoàn thành thỏa mãn $s + c_i \le \ell_{p_i}$.
  • Tổng thời gian phạt là tổng thời điểm hoàn thành của tất cả các bài toán đã giải được.

Cho $n$, $t$, cùng các tham số $p_i$ và $c_i$ cho mỗi bài toán, hãy xác định xem có tồn tại một thứ tự giải các bài toán sao cho:

  • Tất cả $n$ bài toán đều được giải.
  • Tổng thời gian phạt nhỏ hơn nghiêm ngặt so với $t$.

Nếu tồn tại một cách sắp xếp như vậy, hãy in ra YES; ngược lại, in ra NO.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $q$ ($1 \le q \le 10^5$), số lượng bộ kiểm tra. Với mỗi bộ kiểm tra:

Dòng đầu tiên chứa bốn số nguyên: $n$, $\ell_1$, $\ell_2$, và $\ell_3$ ($1 \le n \le 10^5$, $1 \le \ell_1, \ell_2, \ell_3 \le 3 \cdot 10^7$), biểu thị số lượng bài toán và thời điểm rời đi (tính bằng phút sau khi kỳ thi bắt đầu) của ba đồng đội.

Mỗi dòng trong $n$ dòng tiếp theo chứa hai số nguyên $p_i$ và $c_i$ ($1 \le p_i \le 3$, $1 \le c_i \le 300$), trong đó $p_i$ biểu thị đồng đội được chỉ định cho bài toán $i$, và $c_i$ là thời gian cần thiết (tính bằng phút) để họ hoàn thành bài đó.

Dòng cuối cùng chứa một số nguyên duy nhất $t$ ($1 \le t \le 10^{13}$), biểu thị tổng thời gian phạt của đội vô địch.

Tổng của $n$ trên tất cả các bộ kiểm tra không vượt quá $10^5$.

Kết quả

Với mỗi bộ kiểm tra, nếu tồn tại một thứ tự giải các bài toán thỏa mãn các ràng buộc (tất cả các bài toán đều được giải, thời gian phạt nhỏ hơn nghiêm ngặt so với $t$), hãy in ra YES; ngược lại, in ra NO.

Ví dụ

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.