题目描述

高橋君はすぬけ君たちを捕まえようとしています。

$2$ 次元座標平面上にいくつか穴があいており、すぬけ君たちの巣につながっています。

これから $N$ 匹のすぬけ君が穴から出てきます。$i$ 番目のすぬけ君は時刻 $T_i$ に座標 $(X_i,Y_i)$ の穴から出てきて、大きさは $A_i$ であることがわかっています。

高橋君は時刻 $0$ に座標 $(0,0)$ におり、以下の $2$ 種類の移動ができます。

• $x$ 軸方向に単位時間あたり $1$ 以下の速さで移動する
• $y$ 軸正方向に単位時間あたり $1$ 以下の速さで移動する

$y$ 軸負方向に移動することはできません。

すぬけ君が穴から出てきたのと同じ時刻に同じ座標に高橋君がいるとき、かつ、そのときに限り、高橋君はすぬけ君を捕まえることができます。
すぬけ君を捕まえるのにかかる時間は無視できます。

高橋君が適切に行動したとき、捕まえることができるすぬけ君の大きさの合計の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $T_1$ $X_1$ $Y_1$ $A_1$ $T_2$ $X_2$ $Y_2$ $A_2$ $\vdots$ $T_N$ $X_N$ $Y_N$ $A_N$

输出格式

答えを整数として出力せよ。

题目大意

二维平面直角坐标系中，你初始位于 $(0, 0)$，每个时刻可以任意向上，左，右走一步，即步进 $1$ 的距离。存在 $n$ 条收益，当你在 $T_i$ 时刻走到坐标 $(X_i, Y_i)$ 的话就能够获得收益 $A_i$，你需要最大化收益，输出最大值。

3
1 0 0 100
3 2 1 10
5 3 1 1

101

2
100 0 1 1
200 1 0 10

10

10
797829355 595605750 185676190 353195922
913575467 388876063 395940406 533206504
810900084 201398242 159760440 87027328
889089200 220046203 85488350 325976483
277429832 161055688 73308100 940778720
927999455 429014248 477195779 174616807
673419335 415891345 81019893 286986530
989248231 147792453 417536200 219371588
909664305 22150727 414107912 317441890
988670052 140275628 468278658 67181740

1553741733

提示

制約

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ T_i\ \leq\ 10^9$
• $0\ \leq\ X_i,Y_i\ \leq\ 10^9$
• $1\ \leq\ A_i\ \leq\ 10^9$
• $(T_i,X_i,Y_i)$ は相異なる
• 入力に含まれる値は全て整数である

Sample Explanation 1

- 座標 $(0,0)$ で待機し、時刻 $1$ に $1$ 番目のすぬけ君を捕まえる - 座標 $(3,1)$ へ移動し、時刻 $5$ に $3$ 番目のすぬけ君を捕まえる $1$ 番目と $2$ 番目のすぬけ君を両方とも捕まえることはできないので、これが最大です。

Sample Explanation 2

$y$ 軸負方向には移動できないため、$1$ 番目のすぬけ君を捕まえた後、$2$ 番目のすぬけ君を捕まえることはできません。