配点 : $600$ 点

問題文

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

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

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

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

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

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

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

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

制約

• $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)$ は相異なる
• 入力に含まれる値は全て整数である

入力

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

$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$

出力

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

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

101

• 座標 $(0,0)$ で待機し、時刻 $1$ に $1$ 番目のすぬけ君を捕まえる
• 座標 $(3,1)$ へ移動し、時刻 $5$ に $3$ 番目のすぬけ君を捕まえる

$1$ 番目と $2$ 番目のすぬけ君を両方とも捕まえることはできないので、これが最大です。

2
100 0 1 1
200 1 0 10

10

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

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