Robotic Cow Herd

Bessie is hoping to fool Farmer John by building a herd of K realistic robotic cows (1 \leq K \leq 100,000).

It turns out that building a robotic cow is somewhat complicated. There are N (1 \leq n \leq 100,000) individual locations on the robot into which microcontrollers must be connected (so a single microcontroller must be connected at each location). For each of these locations, Bessie can select from a number of different models of microcontroller, each varying in cost.

For the herd of robotic cows to look convincing to Farmer John, no two robots should behave identically. Therefore, no two robots should have exactly the same set of microcontrollers. For any pair of robots, there should be at least one location at which the two robots use a different microcontroller model. It is guaranteed that there will always be enough different microcontroller models to satisfy this constraint.

Bessie wants to make her robotic herd as cheaply as possible. Help her determine the minimum possible cost to do this!

SAMPLE INPUT:

3 10
4 1 5 3 10
3 2 3 3
5 1 3 4 6 6

SAMPLE OUTPUT:

Problem credits: Richard Peng and Nathan Pinsker

입력

The first line of input contains N and K separated by a space.

The following N lines contain a description of the different microcontroller models available for each location. The ith such line starts with M_i (1 \leq M_i \leq 10), giving the number of models available for location i. This is followed by M_i space separated integers P_{i,j} giving the costs of these different models (1 \le P_{i,j} \le 100,000,000).

출력

Output a single line, giving the minimum cost to construct K robots.

출처

USACO 2016 December Platinum

#3988

Robotic Cow Herd 1s 128MB

문제

SAMPLE INPUT:

SAMPLE OUTPUT:

입력

출력

출처

#3988 upload 4 done 1 how_to_reg 1

Robotic Cow Herd timer 1s memory 128MB

문제 text_fields

SAMPLE INPUT:

SAMPLE OUTPUT:

입력

출력

출처

역링크 공식 문제집만

#3988

Robotic Cow Herd 1s 128MB

문제