题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

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

输出样例

61