제가 만든 반례는 아니고...

문제 풀다가 반례가 있나 찾아봤는데

문제의 원 출처에서 제공하는 테스트 케이스가 하나 더 있길래 가져왔습니다.

출처 링크는 https://hsin.hr/coci/archive/2... 의 Contest 6 - Task의 문제 4번입니다.

input
8 9
1 5 5 5
1 2 3 4 5
1 2 8
2 7 4
2 3 10
6 7 40
3 6 5
6 8 3
4 8 4
4 5 5
3 4 23

output
40