这里是跳蚤国中央广播电台，现在为您转播的是著名人类智慧大师 picks 博士与人工智能 betacome 之间的第二轮赛事。

这一场交锋的规则由网友 Po***QQ 提供，这位网友也将获得由不想跳的跳蚤不是好跳蚤——最强跳蚤跳跳跳公司提供的金牌跳蚤一只。

在刚刚结束的第一轮比赛中，因为 picks 博士在关键时刻出现了失误，他惜败给了 betacome。众所周知，A 先生在比赛前夕接受采访时，曾经说过相信 picks 博士可以以全胜的战绩战胜 betacome，请问 A 先生您现在怎么看？

“我仍然觉得 picks 博士的赢面要大一点，第一轮可能是因为他没有调整好心态，在比赛最后的水平堪比业余选手 m**o，这是非常反常的，如果他能够避免这样的失误的话，我觉得仍然觉得人类智慧可以取得最终的胜利。”

好，现在，我们可以看到，第二轮的比赛已经开始了，A 先生您能给我们简要介绍一下这一轮比赛的规则吗？

“好的，相信大家都玩过 osu 吧，这一场的规则来自 osu 的 ctb 模式。其实本来的规则是其他的模式，但是在 betacome 展示了它鬼畜的手速之后，经过比赛委员会的紧急讨论，决定把规则临时改成 ctb 模式。”

“简要来讲，你有一个盘子，时刻 $0$ 时你可以把盘子放到数轴上的任何一个整数坐标处，接着每一时刻你可以把盘子往左移动一个单位、往右移动一个单位或者不动。接着系统生成了 $n$ 个水果，第 $i$ 个水果会在第 $b_i$ 时刻出现在 $a_i$ 坐标处，保证 $b_i$ 单调递增。如果你的盘子在 $b_i$ 时刻恰好出现在 $a_i$ 处，那么就能接到这个水果。”

“最后一个水果落下后，游戏结束。分数用这个方式计算，定义变量 $K$，最开始 $K$ 是 $0$，按照顺序考虑每一个水果，如果你接到了当前水果，那么把 $K$ 加一，否则你的得分将加上 $K^2$ 并将 $K$ 清零，游戏结束后你的得分还会加上游戏结束时的 $K^2$。即你的得分是每一段连续接到水果的极长区间的长度平方和。”

好的，谢谢 A 先生，看来这场赛事的规则还是非常有趣的呀。现在我们节目组已经拿到了这场赛事中使用的水果信息（即数组 $a$ 与数组 $b$），A 先生您能帮我们计算双方可以拿到的最高分吗？

“当然，我们可以非常容易的算出来理论的最高分是****。” 出乎意料地，AcrossTheSky 居然一下子就说出了答案。

了解 AcrossTheSky 真实智力的你觉得这非常反常，你有理由怀疑 AcrossTheSky 是随便报了一个数字出来。所以你决定亲自计算一下答案，来检验一下 AcrossTheSky 是不是在瞎 BB。

输入格式

第一行一个正整数 $n$ ，表示水果的个数。

接下来 $n$ 行，第 $i$ 行包含两个空格分隔的正整数 $a_i,b_i$，表示第 $i$ 个水果会在第 $b_i$ 时刻出现在 $a_i$ 坐标处，保证 $b_i$ 单调递增。

输出格式

输出一行一个正整数，表示这场赛事中双方可以拿到的最高分。

样例一

input

5
2 1
8 2
10 3
5 6
5 8

output

5

explanation

接住第 $1,4,5$ 或者第 $2,4,5$ 个水果，得分为 $1^2+2^2=5$ 。

容易证明这是得分最高的方案。

样例二

input

10
5 1
6 2
10 5
2 6
10 7
4 17
9 19
9 24
8 25
1 28

output

14

explanation

一种得到最高分的方案是，接住第 $1,2,5,7,8,9$ 个果子，总得分为 $2^2+1^2+3^2=14$ 。

样例三

见样例数据下载。这个数据中$n=1000$ 。

限制与约定

由于一些原因，本题使用捆绑测试。每个子任务有若干个测试点，分为 $5$ 个子任务，你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

对于所有数据，$1\le n\le 5\times {10}^5$，$1\le a_i,b_i\le {10}^9$

时间限制：$2\mathtt{\text{s}}$

空间限制：$128\mathtt{\text{MB}}$

下载

样例数据下载