大样例下载

题目描述

这是一个改编的跳格子游戏。

有 $N$ 个格子。

你需要逐个跳跃，即先跳到第 $1$ 个格子里，再跳到第 $2$ 个格子里，……，直到跳到第 $N$ 个格子里。

第 $i$ 个格子里写着两个整数 $L_i、R_i ( L_i ≤ R_i )$。

当你跳到第 $i$ 个格子时，你可得到闭区间 [Li, Ri] 中的任意一个整数。

最后，把你得到的 $N$ 个数求平方和，即为你一次游戏的得分。

你可以玩这个游戏无数次。每次游戏都是独立的。

问：你最多可以得到多少个不同的得分？

输入格式

第一行：一个整数 $N$；

接下来 $N$ 行：每行两个整数 $L_i, R_i$。数据保证 $L_i ≤ R_i$。

输出格式

一个整数，表示答案。

样例输入

2
1 2
1 3

样例输出

5

样例解释

$1^2 + 1^2 = 2$

$1^2 + 2^2 = 5$

$1^2 + 3^2 = 10$

$2^2 + 1^2 = 5$

$2^2 + 2^2 = 8$

$2^2 + 3^2 = 13$

一共可以得到 $2, 5, 8, 10, 13$ 五个不同的得分。

数据范围

100%的数据，$1 ≤ N, L_i, R_i ≤100$