配点 : $600$ 点

問題文

AtCoder 社が開発したゲーム『スヌケトゥーン』は、プレイヤーがすぬけ君を操作して水鉄砲から飛んでくる水を回避するゲームです。

ゲームのステージは無限に続く数直線からなり、ゲーム開始時点ですぬけ君は地点 $0$ にいます。 ゲーム開始直後から、すぬけ君は $1$ 秒ごとに「 $1$ 小さい地点に移動」「 $1$ 大きい地点に移動」「動かない」の $3$ 択から行動を選べます。より厳密には、すぬけ君がゲーム開始後 $t$ 秒 $(t \geq 0$, $t$ は整数$)$ の時点で地点 $p$ にいるとき、 $t+1$ 秒の時点では地点 $p-1$ ・地点 $p$ ・地点 $p+1$ の $3$ ヵ所のいずれかに行くことができます。

すぬけ君は水鉄砲から発射された水を浴びるとダメージを受けてしまいます。水鉄砲は $N$ 回発射されて、 $i$ 回目の発射は $T_i, D_i, X_i$ を用いて次のように表されます。

• ゲーム開始から $T_i$ 秒後に左右いずれかから水が発射されます。すぬけ君が $T_i$ 秒の時点でいる地点を $p$ としたとき、ダメージを受ける範囲および値は次の通りです。 - $D_i = 0$ のとき、$p \lt X_i$ の範囲にいると $X_i - p$ のダメージを受ける。
  • $D_i = 1$ のとき、$X_i \lt p$ の範囲にいると $p - X_i$ のダメージを受ける。

プロゲーマーの高橋君は、攻略情報をツイートするために $N$ 回目の水鉄砲の発射が終わった後のすぬけ君の合計ダメージを最小化することにしました。高橋君が合計ダメージを最小化するようにすぬけ君を操作したときの合計ダメージを求めてください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq T_1 \lt T_2 \lt \dots \lt T_N \leq 10^9$
• $D_i$ $(1 \leq i \leq N)$ は $0$ または $1$
• $-10^9 \leq X_i \leq 10^9$ $(1 \leq i \leq N)$
• 入力は全て整数である。

入力

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

$N$

$T_1$ $D_1$ $X_1$

$T_2$ $D_2$ $X_2$

$\vdots$

$T_N$ $D_N$ $X_N$

出力

高橋君が合計ダメージを最小化するようにすぬけ君を操作したときの合計ダメージを出力せよ。

3
1 0 3
3 1 0
4 0 6

7

便宜上 $t$ をゲーム開始から経過した秒数を表す変数とします。全ての水鉄砲の発射が終了するまでのすぬけ君の最適な動きは以下の通りです。

• $t = 0$ のときすぬけ君は地点 $0$ にいます。すぬけ君は $1$ 大きい地点に移動します。
• $t = 1$ のときすぬけ君は地点 $1$ にいて、 $1$ 回目の水鉄砲の発射により $2$ のダメージを受けます。すぬけ君は $1$ 小さい地点に移動します。
• $t = 2$ のときすぬけ君は地点 $0$ にいます。すぬけ君は移動しません。
• $t = 3$ のときすぬけ君は地点 $0$ にいて、 $2$ 回目の水鉄砲の発射によるダメージを受けません。すぬけ君は $1$ 大きい地点に移動します。
• $t = 4$ のときすぬけ君は地点 $1$ にいて、 $3$ 回目の水鉄砲の発射により $5$ のダメージを受けます。

このときすぬけ君は合計で $7$ のダメージを受けるので、 $7$ を出力します。

3
1 0 1
6 1 1
8 0 -1

0

5
1 0 1000000000
2 1 -1000000000
3 0 1000000000
4 1 -1000000000
5 0 1000000000

4999999997