시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 2 2 100.000%

문제

家庭菜園のプロとなった JOI 君は,毎年,自分の畑で IOI 草という植物を育てている.冬に IOI 草の種 をまくと,春に芽が出て決まった背丈まで伸びる.いくつかの IOI 草は秋になると美しい実を付ける.実 を付けた IOI 草は収穫される.実を付けなかった IOI 草は冬になると枯れてしまう.

JOI 君の畑は東西方向に並んだ N 個の区画に分かれており,西から i 番目 (1 ≦ i ≦ N) の区画 i には IOI 草 i が植えられている.IOI 草 i は,春になると背丈 Hi まで伸び,その後は伸びない.IOI 草 i は,実を付 けたならば Pi 円で取引される.実を付けていない IOI 草には商業的価値はない.

春になって畑の様子を見に行った JOI 君は,植えられているいくつかの IOI 草を抜くことにより,IOI 草 の取引により得られる利益を最大化させることにした.IOI 草 i (1 ≦ i ≦ N) を抜くのに Ci 円の費用がかか る.抜いた IOI 草は枯れてしまう.IOI 草は春にのみ抜くことができ,夏や秋に IOI 草を抜くことはでき ない

IOI 草は夏に日光を多く必要とする植物である.ある区画に植えられている IOI 草について,その区画 より番号の小さい区画と番号の大きい区画の両方にその IOI 草より背丈の高い IOI 草が夏に植えられてい ると,その IOI 草は秋に実を付けない.すなわち,IOI 草 i (1 ≦ i ≦ N) が抜かれていないとき,IOI 草 i が 秋に実を付けるのは,夏の段階で区画 1, . . ., 区画 i − 1 に IOI 草 i よりも背丈の高い IOI 草がない場合か, または,区画 i + 1, . . ., 区画 N に IOI 草 i よりも背丈の高い IOI 草がない場合に限る

実を付けた IOI 草の取引価格の合計から,IOI 草を抜くのにかかる費用の合計を引いた値が,JOI 君の利 益となる.JOI 君は IOI 草からいくらの利益を得ることができるだろうか.

JOI 君の畑の情報と,畑に植えられている IOI 草の情報が与えられたとき,JOI 君が得られる利益の最大 値を求めるプログラムを作成せよ.

입력

標準入力から以下のデータを読み込め.

  • 1 行目には,整数 N が書かれている.N は JOI 君の畑の区画数を表す.
  • 続く N 行のうち i 行目 (1 ≦ i ≦ N) には,3 個の整数 Hi, Pi, Ci が空白を区切りとして書かれている. これは,IOI 草 i が春になると背丈 Hi まで伸び,秋に実を付けたときの取引価格が Pi 円であり,抜 くのにかかる費用が Ci 円であることを表す.

출력

標準出力に,JOI 君の利益の最大値を表す整数を 1 行で出力せよ.

제한

  • 3 ≦ N ≦ 100 000.
  • 1 ≦ Hi ≦ 1 000 000 000 (1 ≦ i ≦ N).
  • 1 ≦ Pi ≦ 1 000 000 000 (1 ≦ i ≦ N).
  • 1 ≦ Ci ≦ 1 000 000 000 (1 ≦ i ≦ N).

예제 입력 1

7
22 60 30
46 40 30
36 100 50
11 140 120
38 120 20
24 90 60
53 50 20

예제 출력 1

320

IOI 草 2 と IOI 草 7 を抜いた後の状態を考える.残った IOI 草は下の表のようになる.

IOI 草の番号 1 3 4 5 6
IOI 草の背丈 22 36 11 38 24
秋に実を付けるか ×

IOI 草 1,IOI 草 3,IOI 草 5,IOI 草 6 の取引価格は,それぞれ 60 円,100 円,120 円,90 円 である. IOI 草 2,IOI 草 7 を抜くのにかかる費用は,それぞれ 30 円,20 円である.JOI 君の利益は 60+100+120+ 90 − 30 − 20 = 320 円となり,この値が最大値である.

예제 입력 2

5
18 150 180
18 380 250
18 140 170
17 180 900
14 150 520

예제 출력 2

1000

この入力例では,どの IOI 草も抜く必要はなく,すべての IOI 草が秋に実を付ける.

예제 입력 3

8
52 156 59
15 166 185
16 122 115
24 161 154
44 252 678
32 225 557
44 155 254
59 57 253

예제 출력 3

854