Input
7 4
4
1 6 2
6 2 2
2 4 2
2 7 1
Output
6
Input
4 3
4
2 1 2
1 3 2
3 4 2
4 1 1
Output
3