#2780. 「BalticOI 2016 Day1」上司们

内存限制:256 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: alpha1022

题目描述

某公司有 n 个职员,其职员之间的阶级关系可以用一棵有根树表示,每个结点都是其所有儿子的上司。
每个职员应当分配一个工资。工资是一个正整数,且每个上司的工资必须大于它所有直系下属的工资之和。
你的任务是找到一种工资分配方案,使得以上所有条件满足且工资之和尽量小。

输入格式

第一行包含一个整数 n ,表示职员的个数,职员依次编号为 1,2,\dots,n
接下来 n 行,第 i 行包含一个整数 k_i ,以及一个包含 k_i 个数的数列。这个数列表示第 i 个员工愿意接受的上司。

输出格式

输出所有方案中最小的工资之和,数据保证有解。

样例

样例输入

4
1 4
3 1 3 4
2 1 2
1 3

样例输出

8

数据范围与提示

子任务 分数 数据范围
1 22 2 \leq n \leq 10,\Sigma^n_{i = 1}k_i \leq 20
2 45 2 \leq n \leq 100,\Sigma^n_{i = 1}k_i \leq 200
3 33 2 \leq n \leq 5000,\Sigma^n_{i = 1}k_i \leq 10000