#PU674. USACO 2016 December Contest, Platinum — Problem 3. Robotic Cow Herd

    ID: 1242 传统题 文件IO:roboherd 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec16来源:usaco.orgscoring:equal_test_cases枚举

USACO 2016 December Contest, Platinum — Problem 3. Robotic Cow Herd

USACO 2016 December Contest, Platinum — Problem 3. Robotic Cow Herd

题目描述

Bessie is hoping to fool Farmer John by building a herd of KK realistic robotic cows (1≤K≤100,0001 \leq K \leq 100,000). It turns out that building a robotic cow is somewhat complicated. There are NN (1≤n≤100,0001 \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!

输入格式

The first line of input contains NN and KK separated by a space. The following NN lines contain a description of the different microcontroller models available for each location. The iith such line starts with MiM_i (1≤Mi≤101 \leq M_i \leq 10), giving the number of models available for location ii. This is followed by MiM_i space separated integers Pi,jP_{i,j} giving the costs of these different models (1≤Pi,j≤100,000,0001 \le P_{i,j} \le 100,000,000).

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 10
4 1 5 3 10
3 2 3 3
5 1 3 4 6 6
61
Problem credits: Richard Peng and Nathan Pinsker