[Usaco2016 Dec]Robotic Cow Herd

内存限制：128 MiB 时间限制：10 Sec

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

.It turns out that building a robotic cow is somewhat complicated. There are N (1≤n≤100,000) indiv

idual locations on the robot into which microcontrollers must be connected (so a single microcontrol

ler must be connected at each location). For each of these locations, Bessie can select from a numbe

r 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 ma

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

贝茜想制造K(1 ≤ K ≤ 100,000)个奶牛机器人来玩弄农夫约翰。一个奶牛机器人需要在N个位置分别安装一个控

制器。每个位置有M_i(1 ≤ M_i ≤ 10)种控制器可供选择，并且每种控制器都有自己价值P_{i,j}(1 ≤ P_{i,j}

≤ 100,000,000)。为了使得奶牛机器人看起来像真的一样，因此贝茜要求没有两个机器人拥有完全相同的控制器

——也就是说至少有一个位置选择了不同的控制器。数据保证在这种条件下至少有K种不同的奶牛。请帮助贝茜计

算制造K个这样的机器人的最小花费。

The first line of input contains NN and KK separated by a space.

The following N lines contain a description of the different microcontroller models available for ea

ch location. The iith such line starts with MiMi (1≤Mi≤10), giving the number of models available

for location ii. This is followed by MiMi space separated integers Pi,jPi,j giving the costs of thes

e different models (1≤Pi,j≤100,000,000).

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


			3 10

4 1 5 3 10

3 2 3 3

5 1 3 4 6 6

#4743. [Usaco2016 Dec]Robotic Cow Herd