这题数据不够强，$O(k \log_2k+k+n^2)$ 的贪心可以过，烦请出题人加上 Hack 数据：

input :
3 2 3
1 2 1
2 3 100
101 3
102 1
103 2

output :
2

另外，请大家无视最优解的那两个匿名用户，那是一个屑的错解。

@LCuter