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