103173: [Atcoder]ABC317 D - President

Problem Statement

Takahashi and Aoki are competing in an election.
There are $N$ electoral districts. The $i$-th district has $X_i + Y_i$ voters, of which $X_i$ are for Takahashi and $Y_i$ are for Aoki. ($X_i + Y_i$ is always an odd number.)
In each district, the majority party wins all $Z_i$ seats in that district. Then, whoever wins the majority of seats in the $N$ districts as a whole wins the election. ($\displaystyle \sum_{i=1}^N Z_i$ is odd.)
At least how many voters must switch from Aoki to Takahashi for Takahashi to win the election?

Constraints

• $1 \leq N \leq 100$
• $0 \leq X_i, Y_i \leq 10^9$
• $X_i + Y_i$ is odd.
• $1 \leq Z_i$
• $\displaystyle \sum_{i=1}^N Z_i \leq 10^5$
• $\displaystyle \sum_{i=1}^N Z_i$ is odd.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

1
3 8 1

Sample Output 1

3

Since there is only one district, whoever wins the seat in that district wins the election.
If three voters for Aoki in the district switch to Takahashi, there will be six voters for Takahashi and five for Aoki, and Takahashi will win the seat.

Sample Input 2

2
3 6 2
1 8 5

Sample Output 2

4

Since there are more seats in the second district than in the first district, Takahashi must win a majority in the second district to win the election.
If four voters for Aoki in the second district switch sides, Takahashi will win five seats. In this case, Aoki will win two seats, so Takahashi will win the election.

Sample Input 3

3
3 4 2
1 2 3
7 2 6

Sample Output 3

0

If Takahashi will win the election even if zero voters switch sides, the answer is $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

问题描述

高桥和青木正在进行一场选举。

有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