题目描述

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$ 回目の水鉄砲の発射が終わった後のすぬけ君の合計ダメージを最小化することにしました。高橋君が合計ダメージを最小化するようにすぬけ君を操作したときの合計ダメージを求めてください。

输入格式

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

$N$ $T_1$ $D_1$ $X_1$ $T_2$ $D_2$ $X_2$ $\vdots$ $T_N$ $D_N$ $X_N$

输出格式

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

题目大意

有一个游戏，发生在一条数轴上，最初 $0$ 时刻，Snuke 在 $0$ 号节点。

每过一个时刻，你可以选择向正方向或负方向移动一格，或者不移动。

接下来有 $n$ 个事件，每一个事件用 $T_i,D_i,X_i$ 描述，其中 $T_i$ 表示事件发生时刻，假设 Snuke 此时在 $p$ 点：

• 若 $D_i=0$，Snuke 将会受到 $\max\{0,X_i-p\}$ 的伤害。
• 若 $D_i=1$，Snuke 将会受到 $\max\{0,p-X_i\}$ 的伤害。

请问 $n$ 次事件之后 Snuke 受到的伤害量的最小值。

• $1\le n\le 2\times 10^5$。
• $1\le T_1\le T_2\le \cdots\le T_n\le 10^9$。
• $\forall i\in[1,n],D_{i}\in\{0,1\},-10^9\le X_i\le 10^9$。
• 所有输入均为整数。

3
1 0 3
3 1 0
4 0 6

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

提示

制約

• $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)$
• 入力は全て整数である。

Sample Explanation 1

便宜上 $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$ を出力します。