Простий набір задач
Найскладніше завдання на будь-якому змаганні 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.