Спасибо, что помогаете Хайди! Сегодня второе апреля, но ее снова вызвала Дженни. Шутка еще не закончилась...
Тем временем Хайди решила, что больше не доверяет своим друзьям. Во всяком случае, не слишком доверяет. Ее относительное отсутствие доверия проявляется следующим образом: в то время как ранее ей не пришлось бы посещать одного и того же человека дважды, теперь она может быть уверена лишь в том, что ее не заставят посетить одного и того же друга более чем k раз.
В случае с Дженни первое её посещение в начале учитывается. Ситуация с простой версией задачи соответствует случаю для k = 1.
Это не так плохо, как кажется, поскольку один билет на маршрут между двумя друзьями позволяет Хайди путешествовать между этой парой друзей целый день (в обоих направлениях). Другими словами, как только она платит за путешествие между парой друзей, все дальнейшие путешествия между этой парой бесплатны.
Каково максимальная сумма денег, которые Хайди может потратить на путешествия между друзьями?
Выходные данные
Выведите одно целое число — максимальную сумму денег, которые Хайди может потратить на путешествия между друзьями.
Примечание
В первом пример худший сценарий для Хайди - посетить друзей в следующем порядке: 0, 1, 5, 1, 3, 1, 0, 2, 6, 2, 7, 2, 8. Обратите внимание, что ни один друг не посещается более чем 3 раза.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9 3
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
|
15
|
|
2
|
9 5
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
|
17
|
|
3
|
11 6
1 0 7932
2 1 1952
3 2 2227
4 0 9112
5 4 6067
6 0 6786
7 6 3883
8 4 7137
9 1 2796
10 5 6200
|
54092
|