AT_agc053_d.[AGC053D] Everyone is a winner

有一个包含 $N$ 名参赛者和 $N$ 道题目的竞赛。每位参赛者编号为 $1$ 到 $N$。对于每一位参赛者和每一道题的组合，已知该参赛者解这道题所需的时间为 $1$ 分钟、$2$ 分钟或 $3$ 分钟。对于第 $i$ 位参赛者，在 $N$ 道题目中，有 $A_i$ 道题需要 $1$ 分钟，有 $B_i$ 道题需要 $2$ 分钟，有 $C_i$ 道题需要 $3$ 分钟。

请判断是否存在一种安排，使得每位参赛者可以自由决定解题顺序，并且对于所有 $1 \leq i, j \leq N$，都满足以下条件：

• 设第 $i$ 位参赛者解完前 $i$ 道题所需的时间为 $S$ 分钟，第 $j$ 位参赛者解完前 $i$ 道题所需的时间为 $T$ 分钟，则有 $S \leq T$。

也就是说，是否存在一种安排，使得对于每个 $i$，第 $i$ 位参赛者在解完前 $i$ 道题时可以成为第 $1$ 名（允许并列）。

忽略解完一道题到开始下一道题之间的时间。

给定 $T$ 组测试数据，请分别作答。

输入由标准输入给出。第一行如下：

$T$

接下来有 $T$ 组测试数据，每组格式如下：

$N$ $A_1$ $B_1$ $C_1$ $:$ $A_N$ $B_N$ $C_N$

对于每组测试数据，如果存在满足条件的安排，输出 Yes，否则输出 No。每组测试数据输出一行。判题时不区分大小写。

限制条件

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i, B_i, C_i \leq N$
• $A_i + B_i + C_i = N$
• 所有测试数据中 $N$ 的总和不超过 $2 \times 10^5$

样例解释 1

对于第一个测试用例，例如可以如下安排使条件成立：

• 参赛者 $1$ 按顺序解第 $1$ 题用 $3$ 分钟，第 $2$ 题用 $2$ 分钟，第 $3$ 题用 $2$ 分钟。
• 参赛者 $2$ 按顺序解第 $1$ 题用 $3$ 分钟，第 $2$ 题用 $2$ 分钟，第 $3$ 题用 $3$ 分钟。
• 参赛者 $3$ 按顺序解第 $1$ 题用 $3$ 分钟，第 $2$ 题用 $2$ 分钟，第 $3$ 题用 $1$ 分钟。

由 ChatGPT 4.1 翻译