바이트산으로 가는 길

바이트만은 산장에 묵으며 바이트산의 정상에 오르려고 합니다. 산에는 갈림길이 $n$개 있고 $1$번부터 $n$번까지 번호가 매겨져 있습니다. 산장은 $1$번 갈림길에 있고, 정상은 $n$번 갈림길입니다.

각 갈림길에는 그 갈림길에서 뻗어 나가는 길들 중 정확히 하나를 가리키는 표지판이 하나씩 서 있습니다. 원래는 모든 표지판이 정상 쪽을 가리키지만, 지금은 표지판이 재배치되는 중이라 어떤 길이든 가리킬 수 있습니다. 심지어 정상에 있는 표지판도 어떤 길 하나를 가리키고 있습니다.

안내인은 다음과 같은 형식으로 길을 알려 줍니다. 산장에서 출발해 표지판이 가리키는 길만 따라가다가 갈림길 $s_1$에 도착하면, 그곳에서는 표지판을 무시하고 $s_1$과 $c_1$을 잇는 길을 택합니다. 그다음 다시 표지판을 따라가다가 $s_2$에 도착하면 $s_2$와 $c_2$를 잇는 길을 택하고, 이런 식으로 계속합니다. $i$번째로 이렇게 지도를 보고 길을 고른 뒤에는, 표지판만 따라가면 결국 정상에 도착합니다.

바이트만은 설명이 너무 복잡해지는 것을 원하지 않아서, 지도를 보는 횟수(표지판 대신 직접 고른 길을 택하는 횟수)를 최대 $k$번으로 제한해 달라고 부탁했습니다.

같은 길이나 갈림길을 여러 번 지나가도 됩니다. 바이트만의 여정은 안내인의 모든 지시를 마친 뒤 정상에 처음 도착하는 순간에 끝납니다. 그 전에 정상을 지나쳐도 멈추지 않습니다.

각 길에는 '아름다움' 값이 매겨져 있습니다. 지도를 최대 $k$번 사용하는, 산장에서 정상까지 가는 경로에서 지나간 길들의 아름다움 합의 최댓값을 구하세요.

첫째 줄에 두 정수 $n$과 $k$가 주어집니다 ($1 \le n \le 50\,000$, $0 \le k \le 100$). 각각 갈림길의 수와 바이트만이 지도를 볼 수 있는 최대 횟수입니다. 갈림길은 $1$번부터 $n$번까지 번호가 매겨져 있으며, 산장은 $1$번, 정상은 $n$번입니다.

이어서 $n$개의 줄에 각 갈림길의 정보가 주어집니다. $i$번째 줄은 먼저 정수 $m_i$ ($1 \le m_i \le n-1$)로 시작하는데, 이는 갈림길 $i$에서 뻗어 나가는 길의 수입니다. 그 뒤에 $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}$인 길이 있다는 뜻입니다. 각 줄의 첫 번째 쌍은 갈림길 $i$의 표지판이 가리키는 길입니다.

모든 길은 양방향이고 서로 다른 두 갈림길을 잇습니다. 어떤 두 갈림길도 최대 하나의 길로만 연결됩니다. 각 길은 입력에 두 번씩, 즉 양쪽 끝 갈림길의 목록에 한 번씩 나타나며 두 경우 모두 아름다움이 같습니다. 길의 총 개수는 $100\,000$을 넘지 않습니다.

산장에서 정상까지 지도를 최대 $k$번 사용하는 올바른 경로에서 지나간 길들의 아름다움 합의 최댓값을 정수 하나로 출력하세요. 그러한 경로는 항상 하나 이상 존재함이 보장됩니다.

그림에서 간선은 갈림길을 잇는 길을, 간선 옆의 숫자는 그 길의 아름다움을, 화살표는 각 갈림길의 표지판이 가리키는 길을 나타냅니다.

갈림길 $3$번과 $2$번에서 지도를 두 번 사용하면 $1 \to 3 \to 4 \to 2 \to 5$ 경로가 되고, 이때 아름다움의 합은 $14$입니다.