题目描述

大马与小普正在参加竞选。 共有 $N$ 个选区，其中第 $i$ 个选区共有 $X_i + Y_i$ 个选民，投票给大马的选民有 $X_i$ 个，投票给小普的选民有 $Y_i$ 个（保证 $X_i + Y_i$ 是奇数）。

在每一个选区，得票多者将会获得该区的 $Z_i$ 个席位。在所有的选区中获得席位多者赢得本次竞选。（$\sum_{i=1}^NZ_i 为奇数$）

大马要想赢得本次竞选，问至少有多少选民从小普那里转投大马才可以？

数据规模

• $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是奇数.$

---

输入格式

第一行一个整数 $N$，表示选区数量。

接下来的N行每一行空格隔开的三个数

$X_i\ Y_i\ Z_i$。

输出格式

一行答案。

---

Sample Input 1

1
3 8 1

Sample Output 1

3

Sample Input 2

2
3 6 2
1 8 5

Sample Output 2

4

Sample Input 3

3
3 4 2
1 2 3
7 2 6

Sample Output 3

0

Sample Input 4

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

Sample Output 4

86