题目描述

贝西希望通过建造一群${K}$头逼真的机器奶牛来愚弄农民约翰${（1≤}$${K≤}$${100,000).}$

事实证明，建造一头机器牛有点复杂。有${N（}$${1≤}$${N≤}$${100000）}$机器人上必须连接微控制器的各个位置（因此每个位置必须连接一个微控制器）。对于这些位置中的每一个，贝西可以从许多不同型号的微控制器中进行选择，每个型号的成本都不同。

为了让这群机器牛看起来让农民约翰信服，任何两个机器人的行为都不应该相同。因此，任何两个机器人都不应该拥有完全相同的微控制器。对于任何一对机器人，至少应有一个位置，两个机器人在该位置使用不同 的微控制器模型。可以保证始终有足够多的不同微控制器模型来满足此约束。

贝西想让她的机器人群旧能便宜。帮助她确定这样做的最低成本.

输入格式

第一行输入包含由空格分隔的${N}$和${K}$。

以下${N}$行包含每个位置可用的不同微控制器型号的描述。第${i}$行以${M_i}$开头${（i≤}$${M_≤}$${10）}$ ，给出了位置${i}$可用的模型数量。然后是${Mi}$空间分隔整 数${Pi，}$${j}$给出了这些不同模型的成本${（1}$${≤}$${P_{i，j}}$${≤}$${100,000,000).}$

输出格式

输出一条直线，使建造${K}$个机器人的成本最小。

样例

输入样例

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

输出样例

61