Universal Cup Judging System

Universal Cup

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

あなたと $2$ 人のチームメイトはプログラミングコンテストに参加していますが、期末試験のため、全員が途中で退出しなければなりません。各自には特定の退出時刻 $\ell_i$(コンテスト開始から退出しなければならない時刻までの分数)が定められています。コンテスト後、解説を確認したあなたたちは、各問題がいずれかのメンバーに完全に適していることに気づきました。問題 $i$ はメンバー $p_i$ が解くのに最適であり、誤提出なしで $c_i$ 分で解き切ることができます。残念ながら、試験のプレッシャーのせいで、元のコンテストではうまくいきませんでした。

夢の中で、あなたは生放送で優勝チームの姿を見ました。彼らは全 $n$ 問を解き、合計ペナルティ時間は $t$ でした。目が覚めると、あなたはコンテスト当日の朝に転生していることに気づきました。すべての問題の詳細と優勝チームの成績を完璧に記憶している今、あなたは今回こそ彼らに勝つ方法があるかどうかを判定したいと考えています。

コンテストのルールは以下の通りです:

  • 利用できるコンピュータは $1$ 台のみであるため、問題は順番に($1$ 問ずつ)解かなければならない。
  • 各問題 $i$ はメンバー $p_i$ に割り当てなければならず、そのメンバーは自身の退出時刻 $\ell_{p_i}$ より前に解き始めなければならない。
  • メンバー $p_i$ が時刻 $s$ に問題 $i$ を解き始めた場合、$s + c_i \le \ell_{p_i}$ までに解き終えなければならない。
  • 合計ペナルティ時間は、解かれたすべての問題の完了時刻の総和である。

$n$、$t$、および各問題のパラメータ $p_i$ と $c_i$ が与えられたとき、以下の条件を満たす問題を解く順序が存在するかどうかを判定してください:

  • 全 $n$ 問が解かれる。
  • 合計ペナルティ時間が $t$ 未満である。

そのような順序が存在する場合は YES を、そうでない場合は NO を出力してください。

入力

$1$ 行目には、テストケースの個数を表す単一の整数 $q$($1 \le q \le 10^5$)が含まれます。各テストケースは以下の通りです:

最初の行には、問題の個数と $3$ 人のチームメイトの退出時刻(コンテスト開始からの分数)を表す $4$ つの整数 $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$ 行のそれぞれには $2$ つの整数 $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.