题目描述

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!

奶牛 Besiie 想要得罪一下农夫 John，为此她想造一个由K个仿真机械牛组成的牛群来戏弄 John （$1\le K \le 10^5$）

然而她发现想要造出一只机械牛是一件很复杂的事。在一只机械牛身上有 $N$（$1\le N \le 10^5$）个位置必须装上微型控制器。Bessie 可以选择不同型号的微型控制器装在每个位置上，每种型号有不同的花费。

为了让这群机械牛看上去不那么假，牛群中里面不能有两头相同的牛。也就是说，不能有哪两头牛身上的微型控制器是完全相同的。对于任意两头机机械牛来说，至少要有一个位置，在这个位置上这两头牛装了不同的微型控制器。因为美国科技很发达，所以 Bessie 总能找到足够型号的控制器来满足这个需求。

现在 Bessie 希望她的机械牛群造价尽量的便宜，因为剩下的钱她还要用来卡 $4$ 分 $35$ 秒出两船兵，她请你帮她计算一下最小花费。

输入格式

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 $i$th 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$).

第一行：$N$ 和 $K$，以一个空格分开。

接下来 $N$ 行：以一个整数 $M_i$ 开头，表示这个位置可以装 $M_i$ 种微型控制器，接下来 $M_i$ 个整数 $P_i$，表示第 $i$ 个控制器的花费 $P_i\le 10^8$。

输出格式

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

61

提示

感谢 @ SakuraDance 提供翻译