Sum of Linear Functions

2 secs 1024 MB
take44444's icon take44444

問題文

あなたはこれから,"丁度良い辛さ"が売りのラーメン屋を開こうとしています. そこで,事前に周辺地域の住人NN人に,好きな辛さについてアンケートを取りました. ラーメンの辛さがXXのとき,ii番目の住人(1iN1 \leq i \leq N)の,そのラーメンに対する嬉しさは以下で表されます.(XXが負のとき,XXの絶対値は甘さを表します.)

max(0,Ai×(XBi+Ci))\mathrm{max}(0, A_i \times ( - | X - B_i | + C_i ) )
ただし AiA_iBiB_iCiC_i は全て正の整数

あなたは「おすすめラーメン」の辛さを,NN人の住人の嬉しさの合計が最大となる辛さにしようと考えました. そのような辛さにおける,NN人の嬉しさの合計を求めなさい.

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Ai,Ci1031 \leq A_i, C_i \leq 10^3
  • 1Bi2×1051 \leq B_i \leq 2 \times 10^5
  • 入力はすべて整数

入力

NN
A1 B1 C1A_1 \ B_1 \ C_1
A2 B2 C2A_2 \ B_2 \ C_2
\vdots
AN BN CNA_N \ B_N \ C_N

出力

NN人の住人の嬉しさの合計を最大いくつにすることができるかを11行に出力しなさい.答えが少数となる場合は誤差は10610^{-6}まで許容されますが,整数となる場合は誤差は許容されませんまた,整数となる場合は小数点や余計な0を出力しないでください.

サンプル

入力例1
3
1 10 5
1 12 5
1 16 5
出力例1
9

9.09.09.0009.0009.000000019.00000001などの出力は誤りとなります.

Submit


Go (1.21)