Input
3
2 1
1 0
0 1
Output
19
Input
5
0 0
0 1
0 2
0 3
0 4
Output
2930