#P11703. [ROIR 2025] 个人 OI 比赛的原则

[ROIR 2025] 个人 OI 比赛的原则

题目背景

翻译自 ROIR 2025 D2T3

题目描述

重温一下个人参加 OI 比赛的原则:每道题都要有分!不能有题目得零分。

让我们模拟一个 OI 比赛的过程。假设比赛中有 nn 道题目,第 ii 道题目包含 kik_i 个子任务,第 ii 道题目的第 jj 个子任务可以获得 ci,jc_{i, j} 分。子任务之间是独立的,因此你可以在每道题中选择任意数量的子任务来解答。但是,你不能一个子任务都不选,因为那样这道题得分就是 00 分,这违反了原则。

你想知道,是否可以在遵守原则的前提下,恰好获得 ss 分。

输入格式

第一行输入两个整数 nnss1n1000001 \leq n \leq 1000001s1000001 \leq s \leq 100000),分别表示比赛中的题目数量和所需的总得分。接下来 2n2n 行输入题目的描述,每道题目的描述包含两行:

  • ii 道题目的第一行包含一个整数 kik_i1ki1000001 \leq k_i \leq 100000),表示第 ii 道题目有多少个子任务。
  • ii 道题目的第二行包含 kik_i 个整数 ci,1,ci,2,,ci,kic_{i,1}, c_{i,2}, \dots, c_{i,k_i}1ci,j1000001 \leq c_{i,j} \leq 100000),表示各个子任务的分值。

保证 k1+k2++kn100000k_1 + k_2 + \dots + k_n \leq 100000,且 (k1+k2++kn)s107(k_1 + k_2 + \dots + k_n) \cdot s \leq 10^7

输出格式

如果无解,输出 No

否则,第一行输出 Yes。接下来,输出每道题目选择的子任务。

对于第 ii 道题目,先输出一行一个整数 mim_i1miki1 \leq m_i \leq k_i),表示你选择的子任务数量。接下来在下一行输出 mim_i 个不同的整数 pi,1,pi,2,,pi,mip_{i, 1}, p_{i, 2}, \dots, p_{i, m_i}1pi,jki1 \leq p_{i, j} \leq k_i),表示你选择的第 ii 道题目的子任务编号。

如果有多个方案可以获得恰好 ss 分,可以输出其中任意一个。

2 4
1
2
2
3 1
No
2 4
1
2
2
2 1
Yes
1
1
1
1

提示

本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。

子任务 分数 特殊性质
11 88 n=1n = 1
22 1010 n=2n = 2
33 66 k1+k2++kn20k_1 + k_2 + \dots + k_n \leq 20
44 ki=1k_i = 1
55 1515 ns100000n \cdot s \leq 100000, s1000s \leq 1000
66 5555