AT_abc317_d [ABC317D] President

高桥君和青木君正在进行选举。 共有 $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 \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 翻译