The Way to Bytemountain

Byteman is staying at a mountain hostel and wants to climb to the peak of Bytemountain. The mountain has $n$ trail crossings, numbered from $1$ to $n$. The hostel is at crossing $1$ and the peak is crossing $n$.

At every crossing stands a single signpost that points along exactly one of the trails leaving that crossing. Normally every signpost points toward the peak, but the signposts are currently being reorganized, so a signpost may point along any trail — even the signpost at the peak points along some trail.

A guide gives directions of the following form. Starting at the hostel, keep following the trails indicated by the signposts until you reach crossing $s_1$; there, ignore the signpost and instead take the trail joining $s_1$ and $c_1$. Then follow the signposts again until you reach $s_2$ and take the trail joining $s_2$ and $c_2$, and so on. After the $i$-th such step of consulting the map (taking a chosen trail instead of the signpost trail) at crossing $s_i$, keep following the signposts and you will eventually arrive at the peak.

Byteman does not want the directions to be too complicated, so he asks the guide to consult the map at most $k$ times (that is, to take at most $k$ trails that differ from the signpost trails).

The route may pass through the same trail or crossing several times. Byteman's walk ends the first time he reaches the peak after all of the guide's instructions have been carried out; he may pass through the peak earlier without stopping.

Every trail has a beauty value. Find the maximum possible total beauty of the trails traversed on a route from the hostel to the peak that consults the map at most $k$ times.

The first line contains two integers $n$ and $k$ ($1 \le n \le 50\,000$, $0 \le k \le 100$): the number of crossings and the maximum number of times Byteman may consult the map. Crossings are numbered from $1$ to $n$; the hostel is crossing $1$ and the peak is crossing $n$.

Each of the next $n$ lines describes one crossing. The $i$-th of these lines begins with an integer $m_i$ ($1 \le m_i \le n-1$), the number of trails leaving crossing $i$, followed by $m_i$ pairs $a_{i,j}\ b_{i,j}$ ($1 \le a_{i,j} \le n$, $1 \le b_{i,j} \le 10\,000$), each meaning that a trail leads from crossing $i$ to crossing $a_{i,j}$ and has beauty $b_{i,j}$. The first pair on each line is the trail that the signpost at crossing $i$ points to.

Every trail is bidirectional and joins two different crossings, and any two crossings are joined by at most one trail. Each trail appears twice in the input, once in the list of each of its two endpoints, with the same beauty both times. The total number of trails does not exceed $100\,000$.

Print a single integer: the maximum total beauty of the trails on a valid route from the hostel to the peak that consults the map at most $k$ times. Such a route is guaranteed to exist.

In the figure, the edges are trails joining crossings, the numbers next to the edges are the beauties of the trails, and the arrows show the trail that each signpost points to.

Consulting the map twice, at crossings $3$ and $2$, yields the route $1 \to 3 \to 4 \to 2 \to 5$ with total beauty $14$.