#agc053d. [agc053_d]Everyone is a winner

[agc053_d]Everyone is a winner

题目描述

我们有一个比赛,有 NN 个参赛者和 NN 个问题。参赛者编号为 11NN。对于每对参赛者和问题,我们知道参赛者解决问题所需的时间,可以是 11 分钟、22 分钟或 33 分钟。在这 NN 个问题中,对于参赛者 ii 而言,有 AiA_i 个问题需要 11 分钟解决,BiB_i 个问题需要 22 分钟解决,CiC_i 个问题需要 33 分钟解决。

确定当参赛者可以自由决定解决问题的顺序时,是否可能满足以下条件对于每个 1i,jN1 \leq i, j \leq N

  • SS 是参赛者 ii 解决前 ii 个问题所需的总时间,TT 是参赛者 jj 解决前 ii 个问题所需的总时间。那么,我们有 STS \leq T

换句话说,确定当参赛者解决前 ii 个问题时,忽略他们在问题之间切换所需的时间,是否可能使参赛者 ii(可能并列)获得第一名。

给出 TT 个测试案例,请解决每个案例。

约束条件

  • 1T2×1051 \leq T \leq 2 \times 10^5
  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 0Ai,Bi,CiN0 \leq A_i, B_i, C_i \leq N
  • Ai+Bi+Ci=NA_i + B_i + C_i = N
  • 所有测试案例中 NN 的总和不超过 2×1052 \times 10^5

输入

从标准输入读入数据,格式如下:

TT

接下来,有 TT 个测试案例,每个案例的格式如下:

NN A1A_1 B1B_1 C1C_1 :: ANA_N BNB_N CNC_N

输出

对于每个测试案例,如果满足题目中的条件,则输出 Yes,否则输出 No。每个案例占一行。(判题器区分大小写:我们将接受大写和小写字母)。

示例输入 1

2
3
0 2 1
0 1 2
1 1 1
3
0 2 1
0 0 3
1 1 1

示例输出 1

Yes
No

在第一个测试案例中,满足条件的一种情况如下:

  • 参赛者 1133 分钟内解决第一个问题,在 22 分钟内解决第二个问题,在 22 分钟内解决第三个问题;
  • 参赛者 2233 分钟内解决第一个问题,在 22 分钟内解决第二个问题,在 33 分钟内解决第三个问题;
  • 参赛者 3333 分钟内解决第一个问题,在 22 分钟内解决第二个问题,在 11 分钟内解决第三个问题。