Description

ArcticBa 打开了海战游戏《WWS》，并加入了一局比赛。

比赛准备期间，$n$ 条战舰按顺序排成一排，战舰分为敌我两个阵营，每艘战舰都拥有生命值 $h_i$ 和火力值 $a_i$。比赛开始前，ArcticBa 可以执行任意次（包括 $0$ 次）以下操作：选择任意 $2$ 艘 相邻 的战舰，改变这 $2$ 艘战舰的阵营（己方战舰变为敌方战舰，敌方战舰变为己方战舰）。

比赛开始后，所有敌方战舰会对所有己方战舰进行炮击，造成的伤害为敌方所有战舰火力值之和 $A$。若己方所有战舰生命值之和 $H$ 小于等于 $A$，则 ArcticBa 输了这局比赛；反之，若己方所有战舰生命值之和 $H$ 大于 $A$，则己方剩余生命值为 $H-A$，且 ArcticBa 赢了这局比赛。

ArcticBa 想要成为《WWS》高手，他想提前知晓这局比赛是否能赢，以及如果能赢，最后剩余生命值之和 $H-A$ 的最大值是多少。

Format

Input

第一行一个正整数 $n$ $(2 \leq n \leq 2\times10^5)$，表示战舰数量。

接下来 $n$ 行，每行包含三个正整数 $h_i,a_i,s_i$ $(1 \leq h_i,a_i \leq 10^9; s_i \in \{0, 1\})$，分别表示第 $i$ 个战舰的生命值，火力值和归属阵营。其中，$s_i=0$ 代表己方阵营，$s_i=1$ 代表敌方阵营。

Output

若 ArcticBa 无论如何操作最终都会输掉这局比赛，输出 $-1$。

若 ArcticBa 可以赢得比赛，请输出一个整数，表示赢得比赛时剩余生命值之和 $H-A$ 的最大值。

Samples

3
218 278 1
212 105 1
21 70 0

451

2
298 234 1
30 51 0

247

2
10 200 1
10 200 0

-1

Limitation

1s, 1024KiB for each test case.