Input
3 2
8 3 8
1 2
2 3
Output
0
Input
3 2
8 12 8
1 2
2 3
Output
2