Простой набор задач
Самое сложное на любом ACM ICPC соревновании - создать набор задач с разумным количеством простых задач. На соревновании Not Easy European Regional Contest эта задача решается так.
Имеется n членов жюри (судей). Они пронумерованы от 1 до n. Судья номер i приготовил p[i] простых задач перед встречей жюри. Каждая задача имеет сложность от 0 до 49 (чем больше тем тяжелее). Каждый судья также знает большое (например бесконечное) количество трудных задач (их сложность равна 50). Для соревнования во время встречи жюри следует выбрать k задач.
Они начинают предлагать задачи в порядке возрастания номеров судей. Первый судья предлагает первую задачу со своего списка оставшихся легких задач (или трудных, если все свои легкие он уже предложил). Предлагаемая задача будет выбрана на соревнование, если ее сложность больше или равна общей сложности уже выбранных задач, иначе она считается слишком легкой. Затем второй судья делает то же самое и т.д .; после n - го судьи свои задачи снова предлагает первый, и так далее. Описанная процедура прекращается, как только будет выбрано k задач.
Если все судьи предложили все свои легкие задачи, но при этом они до сих пор выбрали менее k задач, то они начинают вносить в список соревнования тяжелые задачи чтобы завершить его составление.
Вам следует вычислить сложность набора задач, составленного жюри.
Входные данные
Первая строка содержит количество судей n (2 ≤ n ≤ 10) и количество задач k (8 ≤ k ≤ 14). i-ая из следующих n строк содержит описание задач, подготовленных i-ым судьей. Она начинается значением p[i] (1 ≤ p[i] ≤ 10), за которым следует p[i] неотрицательных целых чисел между 0 и 49 - сложности задач, приготовленных i-ым судьей в том же порядке, в котором он будет их предлагать.
Выходные данные
Вывести одно число - общую сложность всех выбранных задач.
Объяснение
В первом примере сначала будут выбраны три задачи со сложностями 0, 1 и 1. Далее первый судья предложит задачу со сложностью 3 и она будет выбрана. Задача второго судьи со сложностью 1 будет отклонена, так она будет считаться слишком простой. Следующие задачи, предложенные третьим, первым и вторым судьями, будут выбраны (их сложности равны соответственно 5, 12 и 23). Следующие три задачи со сложностями 17, 1 и 20 будут отклонены, и набор будет завершен задачей со сложностью 49. Так что общая сложность набора задач составит 94.
Во втором примере сначала будут выбраны три задачи со сложностями 1, 1 и 2. Вторая задача первого судьи (со сложностью 3) слишком проста. У второго судьи закончились простые задачи, поэтому он предлагает задачу со сложностью 50, которая принимается. Задача третьего судьи со сложностью 5 не выбирается. Жюри принимает решение выбрать еще 6 сложных задач, что в сумме дает сложность 54 + 6 · 50 = 354.