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