1009. 大改革

题目描述

被任命为帝国首相，你决心进行一场声势浩大的改革。 帝国的事务被分为 n 个方面，第 i 个方面的当前值为 0。 你将帝国的势力分为 2 个派系，鹰派与鸽派。 你希望将第 i 个方面的值调整为 ti，鹰派期望第

i 个方面的值为 ai，鸽派期望第 i 个方面的值为 bi。 你的一次操作是，选定第 i 个方面，将它的值增加或减少 1。当然，当改革趋向某

个派系的期望时，它会提供动力；当改革偏离某个派系的期望时，它会进行阻挠。当你已经进行的改革非常符合或非常违背某个派系的期望（由给定的阈值参数 c 刻画），它将会顺从或激进化。具体地，对于一次将第 i 个方面的值变动 d ∈ {−1, 1} 的操作，若某派系对该方面的期望值为 w ∈ {−1, 0, 1}，且该派系在操作前的当前满意度为 S：

• 若 d = w，提供动力 [S ≥ c] + [S ≥ −c]，然后该派系满意度变为 S + 1；

• 若d= w，提供动力 −([S ≤ c] + [S ≤ −c])，然后该派系满意度变为 S − 1。 其中，两派系的满意度初始均为 0。

注：[A] 为艾弗森括号，当条件 A 成立时为 1，否则为 0。你必须且只能对所有满足 ti = 0 的方面各进行一次操作（使其值从 0

变为 ti）。请合理规划这若干次操作的顺序，使得执行所有操作后，

两派系提供的动力总和最大。

输入格式

第一行包含一个整数 T，表示测试用例的数量。 对于每个测试用例：第一行包含两个整数 n 和 c，表示方面的数量和阈值参数。 随后 n行，每行包含三个整数 ti, ai, bi，分别表示你对第 i 项改革的希望值、

鹰派的期望值和鸽派的期望值。 数据保证：T ≤ 50，1 ≤ n, c ≤

10000，−1 ≤ ti, ai, bi ≤ 1。

输出格式

对于每个测试用例输出一个整数，代表你能获得的最大动力总和。

样例输入

2
4 1
1 1 0
-1 -1 -1
1 0 1
1 -1 -1
3 2
1 1 1
-1 1 -1
1 -1 1

样例输出

2
3

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第10场）