题目描述

小可和小达发现了一座神奇的糖果屋。糖果屋里共有 $N$ 袋糖果。

第 $i$ 袋糖果中，原本装有 $X_i$ 颗红色糖果和 $Y_i$ 颗蓝色糖果，总颗数 $X_i + Y_i$ 恰好是奇数。

此外，每袋糖果上还贴有一个价值标签 $Z_i$。

两人决定玩一个游戏来分配这些糖果：

在每一袋糖果中，数量更多的那种颜色将“赢得”这袋糖果，获胜的颜色所属的人可以获得该袋糖果对应的全部价值 $Z_i$。

由于每袋糖果的总数都是奇数，所以每一袋都一定会分出胜负，不会出现平局。

游戏的总价值为所有糖果袋的价值之和 $\sum_{i=1}^N Z_i$，且保证总价值为奇数。总价值更高的一方将赢得整座糖果屋。

一开始，小可拥有所有红色糖果，小达拥有所有蓝色糖果。

但小可可以使用一种魔法：对任何一颗蓝色糖果施法，就能把它变成红色糖果。每施法一次，被施法的糖果就会永久改变颜色，而且小达无法阻止。

小可不想浪费魔法，他只想施最少的魔法，来让红色方（他自己）最终获得的总价值严格超过蓝色方。

请问，小可最少需要施多少次魔法（即最少需要把几颗蓝色糖果变成红色），才能在游戏中获胜？

输入格式

第一行输入一个整数 $N$，表示糖果的袋数。

接下来的 $N$ 行，每行依次输入三个整数 $X_i$、$Y_i$ 和 $Z_i$，分别代表第 $i$ 袋糖果中红色糖果的数量、蓝色糖果的数量以及该袋糖果的价值。每行的三个整数之间用空格分隔。

输出格式

请输出小可最少需要施法的次数（最少需要变红的蓝色糖果数）。

样例

1
3 8 1

3

2
3 6 2
1 8 5

4

3
3 4 2
1 2 3
7 2 6

0

10
1878 2089 16
1982 1769 13
2148 1601 14
2189 2362 15
2268 2279 16
2394 2841 18
2926 2971 20
3091 2146 20
3878 4685 38
4504 4617 29

86

样例1解释

只有 $1$ 袋糖果，谁能在这袋中颜色颗数多，谁就获得价值 $1$ 并赢得游戏。

最初红色有 $3$ 颗，蓝色有 $8$ 颗。小可如果把其中 $3$ 颗蓝色糖果变成红色，则红色变为 $6$ 颗，蓝色变为 $5$ 颗，红色颗数多于蓝色，小可获得整袋价值 $1$，从而获胜。最少需要 $3$ 次魔法。

样例2解释

有两袋糖果，价值分别为 $2$ 和 $5$。最初：

第 $1$ 袋：红 $3$，蓝 $6$，蓝色多于红色，小达获 $2$ 分。

第 $2$ 袋：红 $1$，蓝 $8$，蓝色多于红色，小达获 $5$ 分。

小可若在第 $2$ 袋上施法 $4$ 次，将 $4$ 颗蓝变红，该袋变为红 $5$，蓝 $4$，小可获得这袋的 $5$ 分；第 $1$ 袋仍为小达的 $2$ 分。总分 $5:2$，小可获胜。最少需要 $4$ 次魔法。

样例3解释

在完全不使用魔法的情况下，小可已经能获得超过一半的总价值，因此答案为 $0$。

数据范围

对于 $30\%$ 的时间，$1\le N\le 20$。

对于 $100\%$ 的数据，$1 \leq N \leq 100$，$0 \leq X_i, Y_i \leq 10^9$，$X_i + Y_i$ 为奇数，$1 \leq Z_i$，$\sum_{i=1}^N Z_i \leq 10^5$，$\sum_{i=1}^N Z_i$ 为奇数。