test 3 failed: achieved min dist 2 < optimal 4
input:
1
2 1 4
4 0
output:
2