问题描述

在一款名为Snuketoon的游戏中，由AtCoder, Inc.开发，玩家扮演Snuke来躲避水枪喷射的水。

该平台由一个无限数线组成，在游戏开始时，Snuke位于点0。
从游戏开始时，Snuke每秒可以进行以下三种移动之一：向负方向移动1个单位，向正方向移动1个单位，或保持静止。更正式地说，如果Snuke在游戏开始后的t秒（t≥0，t为整数）处于位置p，则在t+1秒时他的位置可能是p-1、p或p+1。

Snuke会因为被水枪浸湿而受到伤害。水枪会射击N次，第i次射击由Ti、Di和Xi表示。

• 在游戏开始后的Ti秒，水从左侧或右侧射出。设此时Snuke的位置为p。如果他在特定范围内，他将承受以下伤害。
  • 当Di = 0时，如果他处于范围p<Xi，则承受X i - p点的伤害。
  • 当Di = 1时，如果他处于范围Xi<p，则承受p - X i点的伤害。

职业玩家Takahashi希望最小化Snuke在第N次射击结束后所受的总伤害，以在游戏中发布一条推文。找出玩游戏时Snuke所受的总伤害的最小值。

约束条件

• 1≤N≤2×10^5
• 1≤T1<T2<⋯<TN≤10^9
• Di（1≤i≤N）为0或1。
• −10^9≤Xi≤10^9（1≤i≤N）
• 输入中所有值均为整数。

输入

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

N T1 D1 X1 T2 D2 X2 ⋮ TN DN XN

输出

打印玩游戏时Snuke所受的伤害点数。

示例输入1

3
1 0 3
3 1 0
4 0 6

示例输出1

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。

示例输入2

3
1 0 1
6 1 1
8 0 -1

示例输出2

0

示例输入3

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

示例输出3

4999999997