分数: 400 点
问题陈述
高桥和青木正在参加选举。
有 N 选区。的 i第区有 X_i + Y_i 选民,其中 X_i 是高桥和 Y_i 是青木的。 (X_i + Y_i 始终是奇数。)
在每个选区,多数党赢得全部胜利 Z_i 该选区的席位。那么,无论谁赢得议会多数席位 N 整个地区在选举中获胜。 (\displaystyle \sum_{i=1}^N Z_i 是奇数。)
至少有多少选民必须从青木转向高桥,高桥才能赢得选举?
约束
- 1 \leq N \leq 100
- 0 \leq X_i, Y_i \leq 10^9
- X_i + Y_i 是奇数。
- 1 \leq Z_i
- \displaystyle \sum_{i=1}^N Z_i \leq 10^5
- \displaystyle \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
示例输出 1
3
由于只有一个选区,谁赢得该选区的议席,谁就赢得选举。
如果该选区的青木三名选民转投高桥,则高桥将有六名选民,青木五名,高桥将赢得该席位。
示例输入 2
2 3 6 2 1 8 5
示例输出 2
4
由于第二选区的议席多于第一选区,高桥必须赢得第二选区的多数席位才能赢得选举。
如果第二选区青木的四名选民转投阵营,高桥将赢得五个席位。在这种情况下,青木将赢得两个席位,因此高桥将赢得选举。
示例输入 3
3 3 4 2 1 2 3 7 2 6
示例输出 3
0
如果即使零选民倒戈高桥也会赢得选举,答案是 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
示例输出 4
86