Byteman 今天起得很早，天刚蒙蒙亮。他计划前往 Bytemountain 的山顶，因此在前一天晚上住在 Lower Bytehills 风景如画的山脉中间的一家山间旅舍里。由于 Bytemountain 是该山脉中最高的山峰，在每个步道交叉口都有一个路标指向通往山顶的步道。

在山间旅舍，Byteman 遇到了一位对 Lower Bytehills 了如指掌的向导。向导告诉 Byteman，路标正在重新调整，因此他不应该过于依赖路标。特别地，Bytemountain 的山顶本身也是一个交叉口，在这个交叉口处甚至有一个路标指向某条“通往” Bytemountain 的步道！

向导将向 Byteman 解释如何到达山顶。幸运的是，所有的步道交叉口都从 $1$ 到 $n$ 编号，每个交叉口都有一块写有该交叉口编号的牌子。向导的指示形式如下：“沿着路标指向的步道行走，直到到达交叉口 $s_{1}$，然后拿出地图，选择连接交叉口 $s_{1}$ 和交叉口 $c_{1}$ 的步道。之后继续沿着路标指向的步道行走，直到到达交叉口 $s_{2}$。然后查看地图，选择连接 $s_{2}$ 和 $c_{2}$ 的步道……最后，当你到达 $s_{i}$ 时，最后一次查看地图，并沿着连接 $s_{i}$ 和 $c_{i}$ 的步道行走。从那时起，如果你继续沿着路标指向的步道行走，你就会到达 Bytemountain 的山顶。”

Byteman 不希望路线的描述过于复杂，因此他向向导询问了一条不需要查看地图超过 $k$ 次的路线。

向导不得不深思熟虑，因为他知道有些步道比其他步道更令人兴奋，他想向 Byteman 展示最有趣的路线。

路线可能会多次经过相同的步道和交叉口（有些步道非常令人兴奋，以至于值得多次访问！）。

Byteman 在使用向导提供的所有指示后，第一次到达山顶时结束他的步行。这意味着 Byteman 在步行过程中可以多次访问 Bytemountain 的山顶，但他只会在所有指示都被使用后才结束步行。

向导提供的路线可以有多有趣？

输入格式

标准输入的第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 50\,000$, $0 \le k \le 100$)，由单个空格分隔。它们分别表示步道交叉口的数量和 Byteman 希望查看地图的最大次数。交叉口编号从 $1$ 到 $n$，山间旅舍位于交叉口 $1$，Bytemountain 的山顶是编号为 $n$ 的交叉口。

接下来的 $n$ 行包含各个步道交叉口的描述。每个交叉口的描述占一行，由空格分隔的整数组成。第一个数字 $m_{i}$ ($1 \le m_{i} \le n - 1$) 表示从该交叉口出发的步道数量。之后是 $m_{i}$ 对数字 $a_{i,j}, b_{i,j}$ ($1 \le a_{i,j} \le n$, $1 \le b_{i,j} \le 10\,000$)，表示从第 $i$ 个交叉口有一条通往交叉口 $a_{i,j}$ 的步道，其美景度为 $b_{i,j}$。第一对数字表示根据该交叉口路标指向通往 Bytemountain 的步道。每条步道都是双向的，连接两个不同的交叉口。每两个交叉口之间最多由一条步道连接。所有步道的总数不超过 $100\,000$。

连接交叉口 $i$ 和 $j$ 的每条步道在输入中会出现两次：第一次出现在第 $i$ 个交叉口的步道列表中，第二次出现在第 $j$ 个交叉口的步道列表中。在这两种情况下，步道的美景度都是相同的。

输出格式

标准输出的第一行也是唯一一行应包含一个整数，表示满足 Byteman 要求的情况下，从山间旅舍到 Bytemountain 山顶的路线中，连续步道美景度之和的最大值。你可以假设至少存在一条这样的路线。

样例

输入

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

输出

14

说明

在上图中，边代表连接相应交叉口的步道，边旁边的数字代表步道的美景度，箭头代表各交叉口路标指向的步道。

向导将要求 Byteman 在编号为 3 和 2 的交叉口查看地图两次。这样，Byteman 的步行路线将沿着 1 → 3 → 4 → 2 → 5 进行。这条路线上步道的总美景度为 14。