17718번 - Growing Vegetables is Fun 2 서브태스크다국어

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

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

春になって畑の様子を見に行った JOI 君は，植えられているいくつかの IOI 草を抜くことにより，IOI 草 の取引により得られる利益を最大化させることにした．IOI 草 i (1 ≦ i ≦ N) を抜くのに C_i 円の費用がかか る．抜いた 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 個の整数 H_i, P_i, C_i が空白を区切りとして書かれている． これは，IOI 草 i が春になると背丈 H_i まで伸び，秋に実を付けたときの取引価格が P_i 円であり，抜 くのにかかる費用が C_i 円であることを表す．

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

• 3 ≦ N ≦ 100 000．
• 1 ≦ H_i ≦ 1 000 000 000 (1 ≦ i ≦ N)．
• 1 ≦ P_i ≦ 1 000 000 000 (1 ≦ i ≦ N)．
• 1 ≦ C_i ≦ 1 000 000 000 (1 ≦ i ≦ N)．