Input
4 1 2
1 2 1 1
Output
0
Input
4 1 1
1 1 2 1
Output
2