로봇 소 무리

시간 제한2초메모리 제한512 MB

요약

로봇마다 각 위치에서 모델 하나씩을 골라야 하고 K대의 로봇이 모두 서로 달라야 할 때, K대를 만드는 최소 총비용을 구한다.

난이도: 어려움10점 중 9점
유형: 힙, 그리디, 조합론, 정렬
정답자: 아직 제출이 없습니다

문제

베시는 진짜 소처럼 보이는 로봇 소 $K$ 마리( $1 \le K \le 100000$ )를 만들어 농부 존을 속이려고 한다.

로봇 소를 만드는 일은 생각보다 까다롭다. 로봇에는 마이크로컨트롤러를 연결하는 자리가 $N$ 개( $1 \le N \le 100000$ ) 있고, 각 자리마다 마이크로컨트롤러를 정확히 하나씩 연결해야 한다. $i$ 번 자리에는 그 자리에 쓸 수 있는 여러 모델 중 하나를 고를 수 있고, 가격은 모델마다 정해져 있다.

무리가 그럴듯해 보이려면 어떤 두 로봇도 똑같이 동작해서는 안 된다. 즉 두 로봇의 마이크로컨트롤러 구성이 완전히 같아서는 안 되고, 어떤 두 로봇을 골라도 서로 다른 모델을 쓴 자리가 적어도 한 곳 있어야 한다. 같은 자리에 있는 두 모델은 가격이 같아도 서로 다른 모델로 센다. 서로 다른 로봇 $K$ 대를 만들 수 있을 만큼의 모델은 항상 주어진다.

베시는 무리를 최대한 싸게 만들려고 한다. 로봇 $K$ 대를 만드는 최소 비용을 구한다.

입력

첫째 줄에 $N$ 과 $K$ 가 공백으로 구분되어 주어진다.

다음 $N$ 개의 줄에는 각 자리에서 고를 수 있는 모델이 주어진다. $i$ 번째 줄은 $i$ 번 자리에서 고를 수 있는 모델의 개수 $M_i$ ( $1 \le M_i \le 10$ )로 시작하고, 이어서 그 모델의 가격 $P_{i,1}, \dots, P_{i,M_i}$ ( $1 \le P_{i,j} \le 100000000$ )가 공백으로 구분되어 주어진다.

출력

로봇 $K$ 대를 만드는 최소 비용을 한 줄에 출력한다.

예제5

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

예제 3

입력

3 1
1 100000000
1 100000000
1 99999999

예상 출력

299999999

예제 4
입력
```
1 10
10 5 3 9 1 7 2 8 4 6 10
```
예상 출력
```
55
```
예제 5
입력
```
2 6
3 4 4 4
2 5 1
```
예상 출력
```
42
```