Snuketoon

题目描述

在由 AtCoder Inc. 开发的游戏 Snuketoon 中，玩家扮演 Snuke，躲避水枪射出的水。

平台是一条无限长的数轴，游戏开始时 Snuke 在点 $0$ 处。

从游戏开始起，Snuke 每秒可以选择以下三种移动之一：向负方向移动 $1$、向正方向移动 $1$，或保持不动。更正式地说，如果 Snuke 在游戏开始 $t$ 秒时（$t \ge 0$，$t$ 为整数）位于点 $p$，则他在 $t+1$ 秒时可以位于 $p-1$、$p$ 或 $p+1$。

Snuke 会被水枪喷出的水淋湿而受到伤害。水枪共发射 $N$ 次，第 $i$ 次发射由 $T_i$、$D_i$ 和 $X_i$ 表示，如下所示。

在游戏开始 $T_i$ 秒时，水从左侧或右侧喷出。设此时 Snuke 的位置为 $p$。如果他在以下范围内，则受到如下伤害。

当 $D_i=0$ 时，如果他在范围 $p \lt X_i$ 内，受到 $X_i-p$ 点伤害。

当 $D_i=1$ 时，如果他在范围 $X_i \lt p$ 内，受到 $p-X_i$ 点伤害。

职业玩家高桥想要让 Snuke 在第 $N$ 次发射结束后受到的伤害总和最小，以便把游戏成绩发布到社交媒体。求以最小伤害为目标进行游戏时，Snuke 受到的伤害总和。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出以最小伤害为目标进行游戏时，Snuke 受到的伤害点数。

样例

3
1 0 3
3 1 0
4 0 6

7

为方便起见，用 $t$ 表示游戏开始后经过的秒数。Snuke 在所有射击结束前的最优移动路线如下。

当 $t=0$ 时，Snuke 在点 $0$，他向正方向移动 $1$。

当 $t=1$ 时，Snuke 在点 $1$，第一次射击使他受到 $2$ 点伤害。他向负方向移动 $1$。

当 $t=2$ 时，Snuke 在点 $0$，他保持不动。

当 $t=3$ 时，Snuke 在点 $0$，第二次射击没有造成伤害。他向正方向移动 $1$。

当 $t=4$ 时，Snuke 在点 $1$，第三次射击使他受到 $5$ 点伤害。

这样，Snuke 共受到 $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

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le T_1 \lt T_2 \lt \dots \lt T_N \le 10^9$
• $D_i$ $(1 \le i \le N)$ 为 $0$ 或 $1$。
• $-10^9 \le X_i \le 10^9$ $(1 \le i \le N)$
• 输入中的所有值均为整数。