광고 배치

시간 제한1초메모리 제한128 MB

요약

최대 7일 범위의 상대적 표시 패턴을 가진 N개의 배너 요청을 순서대로, 하루 최대 K개까지 배치해 시작일부터 마지막 표시일까지 걸리는 기간을 최소화하는 문제입니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그리디, 시뮬레이션, 비트 연산
정답자: 아직 제출이 없습니다

문제

슬라브코는 자신의 웹 페이지에 하루에 최대 K개의 광고 배너만 보여줄 수 있다.

각 광고주는 배너가 처음 표시되는 정확한 날짜를 지정하지는 않는다. 대신 배너가 처음 표시된 날을 1일째로 보았을 때, 그 이후 어떤 상대 날짜에도 배너가 다시 표시되어야 하는지를 요청한다. 하나의 요청에서 첫 표시일부터 마지막 표시일까지의 범위는 최대 7일이다.

슬라브코는 광고 요청을 순서대로 받는다. 요청 A가 요청 B보다 먼저 도착했다면, B의 첫 표시일은 A의 첫 표시일보다 빠를 수 없다.

슬라브코는 첫 배너가 표시되기 시작한 날부터 마지막 배너가 표시되는 날까지의 기간을 가능한 한 짧게 만들고 싶다.

이 기간의 최소 일수를 구하는 프로그램을 작성하라.

입력

첫 줄에 요청의 수 N과 하루에 표시할 수 있는 배너의 최대 개수 K가 주어진다. 1 <= N <= 100, 1 <= K <= 4이다.

다음 N개 줄에는 슬라브코가 받은 순서대로 각 요청의 설명이 주어진다. 각 줄의 첫 번째 정수 R_i는 해당 배너가 표시되어야 하는 총 횟수이다. 이어서 R_i - 1개의 정수가 오며, 이 정수들은 첫 표시일을 1일째로 보았을 때 배너가 추가로 표시되어야 하는 날짜를 뜻한다. 이 날짜들은 오름차순으로 주어진다.

출력

첫 배너가 표시되기 시작한 날부터 마지막 배너가 표시되는 날까지 필요한 최소 일수를 한 줄에 출력한다.

예제3

예제 1
입력
```
1 1
3 3 6
```
예상 출력
```
6
```
예제 2
입력
```
2 1
2 3
2 3
```
예상 출력
```
4
```
예제 3
입력
```
3 2
3 3 6
3 3 7
3 5 6
```
예상 출력
```
7
```