E. 不畏苦暗
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
所谓骑士，就是照亮整片大地的崇高者.
—— 玛嘉烈·临光

"骑士最后的敌人，是这片大地."

"那些本该安分地等待在地上的城市，以人民的血汗为食，竟然开始蠕行前进."

"城市是生活的怪物，去号召他们对抗每一座城，去将最纯真的美好归还给他们！"

"让草原重新成为草原，让天空仍是天空，让人性再次坚定，让荣光永垂不朽！"

"我即是最后的骑士！"

耀骑士临光为了驱散整片卡西米尔的黑暗，将 n 根光枪插成一排. 每个光枪有一个位置 xi 和亮度 vi，对任一整数位置 x, 第 i 个光枪对该位置的影响遵循以下规则：

  • 记该位置与光枪的距离为 d(即从xi 向左/右走 d 个单位能到达 x)
  • 当 d = 0, 1, 2, ..., vi - 1 时，光枪在该位置提供的亮度分别为vi, vi - 1, vi - 2, ..., 1，也就是说，每远离光枪一个位置，亮度减少 1.
  • 当 d ≥ vi 时，该光枪不照亮该位置，即提供的亮度为 0.
某个位置的实际亮度取所有光枪对该位置提供亮度中的最大值.

临光想知道，她到底给卡西米尔提供了多少光芒. 请你计算所有整数位置实际亮度的总和.

Input

第一行一个整数 n (1 ≤ n ≤ 2 × 105)，代表光枪数量；

接下来 n 行，每行两个整数 xi, vi(1 ≤ xi, vi ≤ 1 × 109)，代表第 i 个光枪的位置和亮度. 数据保证位置递增，且同一位置最多有一个光枪.

Output

输出一个整数，代表所有整数位置实际亮度的总和.

Examples
Input
3
1 3
3 2
9 1
Output
12
Input
2
5 4
8 3
Output
21
Note

样例一中，x =  - 1 位置的实际亮度为 1,由第一根光枪提供； x = 0 位置的实际亮度为 2,由第一根光枪提供； x = 1 位置的实际亮度为 3,由第一根光枪提供； x = 2 位置的实际亮度为 2,由第一根光枪提供； x = 3 位置的实际亮度为 2,由第二根光枪提供； x = 4 位置的实际亮度为 1，由第二根光枪提供； x = 9 位置的实际亮度为 1，由第三根光枪提供； 其余位置亮度为 0.

总计为 1 + 2 + 3 + 2 + 2 + 1 + 1 = 12.