쉬운 문제 세트 만들기

ACM ICPC 대회를 준비할 때 가장 어려운 일 가운데 하나는 적당한 수의 쉬운 문제를 담은 문제 세트를 만드는 것이다. Not Easy European Regional Contest에서는 이 일을 다음과 같이 처리한다.

출제자는 $n$명이고 1번부터 $n$번까지 번호가 붙어 있다. $i$번 출제자는 회의 전에 쉬운 문제를 $p_i$개 준비했다. 각 문제의 난이도는 0 이상 49 이하이고, 값이 클수록 어렵다. 모든 출제자는 난이도가 50인 어려운 문제도 사실상 무한히 알고 있다. 출제자들은 이번 회의에서 대회에 쓸 문제 $k$개를 고른다.

제안은 번호가 작은 출제자부터 차례로 한다. 1번 출제자는 아직 제안하지 않은 쉬운 문제 중 첫 번째 문제를 제안하고, 쉬운 문제를 모두 제안했다면 어려운 문제를 제안한다. 제안된 문제의 난이도가 지금까지 선택한 문제의 난이도 합 이상이면 그 문제를 대회 문제로 선택하고, 그렇지 않으면 너무 쉽다고 보고 버린다. 이어서 2번 출제자가 같은 방식으로 제안하며, $n$번 출제자까지 끝나면 다시 1번 출제자부터 제안한다. 문제를 $k$개 선택하는 즉시 이 과정을 멈춘다.

모든 출제자가 준비한 쉬운 문제를 전부 제안했는데도 선택한 문제가 $k$개보다 적다면, 남은 자리는 난이도 합과 상관없이 어려운 문제로 채운다.

출제자들이 만든 문제 세트의 난이도 합을 구하라.

첫째 줄에 출제자 수 $n$과 고를 문제 수 $k$가 주어진다 ($2 \le n \le 10$, $8 \le k \le 14$). 다음 $n$개 줄 중 $i$번째 줄에는 $i$번 출제자가 준비한 문제가 주어진다. 각 줄은 $p_i$ ($1 \le p_i \le 10$)로 시작하고, 이어서 0 이상 49 이하인 정수 $p_i$개가 제안하는 순서대로 주어진다.

선택한 문제의 난이도 합을 정수 하나로 출력한다.

첫 번째 예제에서는 난이도가 0, 1, 1인 문제 세 개가 먼저 선택된다. 이어서 1번 출제자가 난이도 3인 문제를 제안해 선택되고, 2번 출제자가 제안한 난이도 1인 문제는 너무 쉬워서 버려진다. 그다음 3번, 1번, 2번 출제자가 제안한 난이도 5, 12, 23인 문제가 선택된다. 이어지는 난이도 17, 1, 20인 문제 세 개는 선택되지 않고, 마지막으로 3번 출제자가 제안한 난이도 49인 문제가 선택되면서 문제 세트가 완성된다. 난이도 합은 94다.

두 번째 예제에서는 난이도가 1, 1, 2인 문제 세 개가 먼저 선택된다. 1번 출제자의 두 번째 문제는 난이도가 3이라 너무 쉽다. 2번 출제자는 쉬운 문제를 다 썼으므로 난이도 50인 문제를 제안하고, 이 문제는 선택된다. 3번 출제자가 제안한 난이도 5인 문제는 선택되지 않는다. 남은 여섯 자리는 어려운 문제로 채우므로 난이도 합은 $54 + 6 \times 50 = 354$다.