Description

汤姆斯生活在一个等级为 0 的星球上。那里的环境极其恶劣，每天 l2 小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为 N 的星球上天堂般的生活。

有一些航班将人从低等级的星球送上高一级的星球，有时需要向驾驶员支付一定金额的费用，有时却又可以得到一定的金钱。

汤姆斯预先知道了从 0 等级星球去 N 等级星球所有的航线和需要支付(或者可以得到)的金钱，他想寻找一条价格最低(甚至获得金钱最多)的航线。

Format

Input

第一行，一个正整数 N（N《100），如题意。接下来描述 N 个等级的星球连接情况，依次描述等级 1，2，3，……，N。对于第 i 等级的描述，第一行为一个整数 K，表示等级为 i的星球有共有 K 个；紧接着的 K 行，每行依次为编号为 1,2,3,……，K 的星球连接情况；每行中依次该星球与等级为 i-1 的星球编号连接情况。详细情况见附图。

Output

输出所需(或所得)费用。正数表示支出，负数表示收益。

Samples

3
2
1 15 0
1 5 0
3
1 -5 2 10 0
1 3 0
2 40 0
2
1 1 2 5 3 -5 0
2 -19 3 –20 0

-1

Limitation

对于 l00％的数据 N≤100 Ki≤100。