Background

测试啊测试啊啊啊

Description

惊闻世界最长寿男子去世，跑得快的香港记者张宝华决定就此事采访某位神秘的东方人物.不过这位宝华同志还想顺道拜访她的老朋友们，于是她找到了你，想请你帮她给自己规划一条刚好经过所有老朋友住地的路线.
值得一提的是，这位香港记者实在是跑的太快了，甚至快过了时间（雾），于是获得了一项新特性：可以以牺牲1s寿命的方式回到任意曾经来过的地方.也就是说，最终规划的路线中允许回头，而不必要是一条单向线段.且多次到达同一个城市只会产生一次旅行费用.此外，所有的老朋友们都住在不同的城市里，不会有两位老朋友住在同一城市.

Format

Input

每组测试数据第一行有两个整数n，m . n表示需要拜访的老朋友的人数（城市数量）.m=∑▒t_i (t_i的含义见后).第二行至第n行，第i（2≤i≤n）行首先有一个整数t_i，表示从该城市可以到达编号在其后的t_i个不同的城市.该行随后有t_i组数据，每组两个整数，第一个整数p_j表示可以到达城市的编号，第二个整数q_j表示到达该城市需要花费的路费（0≤j≤t_i）.且我们约定，城市编号为1 - n.（即第i(i≥2)行数据表示编号为i-1的城市到编号在i-1之后的其他城市的情况）

Output

一个整数。表示所需的最少旅行费用.

Sample 1

Input

5 8
3 2 2 3 6 5 1
3 3 3 4 5 5 2
1 4 1
1 5 1

Output

7

Limitation

1s, 512MiB for each test case.

Source

Vijos Original