#P17863. 最佳比赛总监

最佳比赛总监

A. 最佳比赛总监

时间限制:3 秒;内存限制:512 MiB。

有 nn 个小组。第 ii 组有 kik_i 名成员,能力值分别为 ai,1,…,ai,kia_{i,1},\ldots,a_{i,k_i}。小组的影响力是剩余成员能力值之和,空组的影响力为 00。

每次操作选择一个非空小组,移除其中能力值最小的一名成员。若有多人并列最小,任选一人。

每次操作结束后,每个小组的影响力都不能超过其他小组影响力之和。初始状态不一定满足此条件。

求最多可以移除多少名成员,并给出一种最优操作序列。

输入格式

第一行是测试组数 T≥1T\ge1。每组第一行是 nn。随后 nn 行,第 ii 行先给出 kik_i,再给出该组的 kik_i 个能力值。

1≤n,ki≤5×1051\le n,k_i\le5\times10^5,1≤ai,j≤1091\le a_{i,j}\le10^9。所有测试的 nn 之和及所有成员数之和均不超过 5×1055\times10^5。

输出格式

每组输出两行:第一行是最大移除人数 mm;第二行是 mm 个小组编号,表示依次从哪个小组移除成员。m=0m=0 时第二行为空。允许任意合法最优解。

3
4
1 1
2 2 4
2 3 4
1 8
1
1 7
2
2 1 1
2 1 1
4
3 2 4 1
1
1
0