题目描述

椅子玩自定义咒刃，一路打到了第三关的银行，他想在黑色大桥无伤看守者之前找点刺激的。

加了模组的银行极大。具体地说，这一关有 $n$ 个战斗场景按顺序排成一行，依次编号为 $1\sim n$ ，椅子一开始在第一个战斗场景，而黑色大桥在第 $n$ 个场景之后。

每个场景在开头有个金门，每个金门里有一把咒刃，每个场景都有一只怪（细胞三爹：拳皇，鸡哥，三刀哥）。

第 $i$ 个场景的咒刃有四个属性：第一刀伤害 $b_i$ ，后摇 $k_i$ ，加速条件杀敌数 $a_i$ ，加速范围 $d_i$ 。

由于上一关的咒刃等级太低，所以椅子必须得砍第一个金门拿到第一把咒刃。除此之外，椅子在后面的任意场景开头都可以砍金门，获得新的咒刃，并用那把咒刃直到下一次砍金门或者到达黑色大桥。

刚拿到第 $i$ 个场景的咒刃时，第一刀会非常刺激，产生 $b_i$ 刺激度，但后摇会降低刺激度 $k_i$ ，直到开始加速。当拿这把刀杀敌数达到 $a_i-d_i$ 时，刺激度会呈朝下的抛物线（二次项系数为 $-1$ ）变化，杀敌数 $a_i$ 时到达顶点，此后刺激度开始降低。一直到杀敌数 $a_i+d_i$ 时，由于长时间保持无伤打怪，刺激度随着疫病上来了，此后又呈二次函数上升......

具体地说，如果带上第 $l$ 个金门的咒刃一直打到第 $r$ 场景结束，将会产生 $f_l(r-l+1)$ 的刺激度。函数 $f_l(x)$ 定义如下：

当 $x\le a_l-d_l$ ， $f_l(x)=-k_lx+b_l$ ； 当 $a_l-d_l < x < a_l+d_l$ ， $f_l(x)=-k_l(a_l-d_l)+b_l+d_l^2-(a_l-x)^2$ ； 当 $x\ge a_l+d_l$ ， $f_l(x)=-k_l(a_l-d_l)+b_l+(x-(a_l+d_l))^2$ 。 （如果你对这类函数需要直观的感受，请参考本题的【提示】部分。）

开了新的金门后，先前的刺激度会停止变化，随后刺激度将加上新的咒刃带来的刺激度。也就是说，把每一把咒刃带来的刺激度累加就是总刺激度。

椅子希望找到一种合适的砍金门方案，使得最终总刺激度最大。但是他正在直播，所以把这个问题交给了你。

【提示】 本题中涉及的 $f_l(x)$ 的直观图如下：

输入格式

第一行一个正整数 $n$ ，表示这一关的场景个数。

接下来 $n$ 行，第 $i$ 行包含四个正整数 $k_i,a_i,b_i,d_i$ ，分别表示第一刀伤害、后摇、加速条件杀敌数和加速范围。

本题的输入文件较大，请使用较快的读入方式。出题人建议尽可能使用快于 $scanf()$ 的读入方式。请注意这里变量的输入顺序和【题目描述】中变量的出现顺序不同。

输出格式

输出仅一行一个整数，表示最大刺激度。

数据范围

对于所有测试点： $1\le n\le 10^6,1\le k_i,b_i\le 10^6,1\le d_i\le a_i\le n$ 。

每个测试点的具体限制见下表：

测试点编号	$n \le$	特殊限制
$1\sim 5$	$5\times 10^3$	无
$6\sim 10$	$10^6$	$a_i=d_i=n$
$11\sim 15$	$10^5$	无
$16\sim 20$	$10^6$	$a_i+d_i\ge n$
$21\sim 25$		无

输入样例 1

5
1 2 8 1
9 3 8 2
4 3 3 3
4 1 2 1
7 2 1 2

输出样例 1

23

输入样例 2

4
1 4 1 4
1 4 2 4
1 4 1 4
1 4 3 4

输出样例 2

35

输入样例 3

4
2 1 8 1
5 2 1 2
3 1 1 1
1 2 1 2

输出样例 3

19

样例解释

对于样例 $1$ ：

依次拿第 $1,3,5$ 把咒刃：

第一把咒刃的刺激度为 $f_1(2)=-1\times (2-1)+8+1^2-(2-2)^2=8$ 。 第二把咒刃的刺激度为 $f_3(2)=-4\times (3-3)+3+3^2-(3-2)^2=11$ 。 第三把咒刃的刺激度为 $f_5(1)=-7\times (2-2)+1+2^2-(2-1)^2=4$ 。

最终总的刺激度为 $8+11+4=23$ 。可以证明，这是可能获得的最大的刺激度。