Description

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

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

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

Input Format

第一行一个正整数N（$N \le 100$）

接下来的数据可分为N个段落

每段的第一行一个整数$K_i$（$Ki \le 100$），表示等级为i的星球有$K_i$个。

接下来的$K_i$行中，第j行有多对整数，依次表示与等级为i，编号为j的星球相连的等级为i-1的星球的编号和此航线需要的费用（正数表示支出，负数表示收益，费用的绝对值不超过1000）。每行以0结束，每行的航线数<=100。

Output Format

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

Sample

输入样例

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

Hint

对于$100\%$的数据 $N \le 100$ $Ki \le 100$;