题目描述

高桥君和青木君正在进行选举。
共有 $N$ 个选区。第 $i$ 个选区有 $X_i + Y_i$ 名选民，其中 $X_i$ 人支持高桥君，$Y_i$ 人支持青木君（$X_i + Y_i$ 均为奇数）。
在每个选区中，多数派将获得该区全部 $Z_i$ 个议席。最终，获得所有选区议席总数过半的一方将赢得选举（$\sum_{i=1}^N Z_i$ 是奇数）。
请问高桥君至少需要让多少名青木派选民转为高桥派，才能赢得选举？

输入格式

输入按以下格式从标准输入读入。

$N$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_N$ $Y_N$ $Z_N$

输出格式

请输出答案。

样例 1

输入

1
3 8 1

输出

3

样例 2

输入

2
3 6 2
1 8 5

输出

4

样例 3

输入

3
3 4 2
1 2 3
7 2 6

输出

0

样例 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

输出

86

说明/提示

限制条件

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

样例解释 1

由于只有 $1$ 个选区，谁获得第 $1$ 个选区的议席谁就能赢得选举。如果让第 $1$ 个选区的 $3$ 名青木派选民转为高桥派，则该区高桥派有 $6$ 人，青木派有 $5$ 人，高桥君即可获得该区议席。

样例解释 2

第 $2$ 个选区的议席数比第 $1$ 个多，因此高桥君必须在第 $2$ 个选区成为多数派才能赢得选举。如果让第 $2$ 个选区的 $4$ 名青木派选民转为高桥派，则高桥君可获得 $5$ 个议席，而青木君只获得 $2$ 个议席，高桥君即可胜选。

样例解释 3

如果即使没有任何青木派选民转为高桥派，高桥君也能赢得选举，则答案为 $0$。

由 ChatGPT 4.1 翻译