Главное правило личных олимпиад
(Время: 2 сек. Память: 256 Мб Сложность: 70%)
Напомним главное правило написания личных олимпиад: по каждой задаче нужно набрать баллы! Нельзя уйти с контеста с нулем по задаче.
Промоделируем тур олимпиады. Пусть на туре предложено n задач, i-я задача состоит из ki подзадач, j-я подзадача i-й задачи приносит ci,j баллов. Зависимостей между подзадачами нет, поэтому можно в каждой задаче выбрать любое множество подзадач и его решить. При этом нельзя выбрать пустое множество, ведь тогда по задаче будет 0 баллов, а это противоречит главному правилу написания личных олимпиад.
Проверьте, можно ли, придерживаясь главного правила личных олимпиад, набрать на туре ровно s баллов.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа n, s (1 ≤ n ≤ 100 000, 1 ≤ s ≤ 100 000) – количество задач в контесте и необходимую сумму баллов, соответственно. Далее следуют описания задач. Описание каждой задачи состоит из двух строк.
Первая строка описания i-й задачи содержит одно целое число ki (1 ≤ ki ≤ 100 000) – количество подзадач в i-й задаче.
Вторая строка описания i-й задачи содержит ki целых чисел ci,1, ci,2, ... , ci,ki (1 ≤ ci,j ≤ 100 000) – баллы за подзадачи.
Гарантируется, что сумма k1 + k2 + ... + kn по всем задачам не превосходит 100 000.
Гарантируется, что произведение (k1 + k2 + ... + kn) · s не превосходит 107.
Выходные данные
В выходной файл OUTPUT.TXT выведите «No» если решения не существует.
В противном случае в первой строке выведите «Yes». Далее необходимо вывести описание решенных подзадач для каждой задачи.
Описание i-й задачи начинается с целого числа mi (1 ≤ mi ≤ ki) – количества решенных подзадач i-й задачи. Далее следуют mi различных целых чисел pi,1, pi,2, ... , pi,mi (1 ≤ pi,j ≤ ki) – номера решенных подзадач в i-й задаче.
Если существует несколько подходящих способов набрать s баллов, выведите любое из них.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 2 4 1 2 2 3 1 | No |
2 | 2 4 1 2 2 2 1 | Yes
1 1 1 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|