Robotic Cow Herd

题目描述

Bessie 希望通过建造一群由 $K$ 头逼真的机器牛组成的牛群来欺骗 Farmer John（$1 \leq K \leq 100,000$）。 事实证明，建造一头机器牛相当复杂。 机器牛上有 $N$ 个需要连接微控制器的位置（因此每个位置都必须连接一个微控制器）。对于每个位置，Bessie 可以从若干种不同型号的微控制器中选择，每种型号的成本各不相同。 为了让这群机器牛在 Farmer John 眼中足够逼真，任意两头机器牛的行为都不应完全相同。因此，任意两头机器牛都不应使用完全相同的一组微控制器。对于任意一对机器牛，至少应存在一个位置使得它们在该位置使用的微控制器型号不同。保证总会有足够多的不同微控制器型号来满足这一约束。 Bessie 希望尽可能低成本地制造这群机器牛。请帮助她确定实现这一目标的最小可能总成本！

输入格式

第一行输入包含 $N$ 和 $K$，以空格分隔。 接下来的 $N$ 行描述每个位置可用的不同微控制器型号。第 $i$ 行以 $M_i$（$1 \leq M_i \leq 10$）开头，表示位置 $i$ 可用的型号数量。随后有 $M_i$ 个以空格分隔的整数 $P_{i,j}$，表示这些不同型号的成本（$1 \le P_{i,j} \le 100,000,000$）。

输出格式

输出一行，给出构造 $K$ 头机器牛的最小成本。

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

61

提示

题目提供者：Richard Peng 和 Nathan Pinsker

标签: USACO|2016|Platinum

来源

USACO|2016|Platinum