题面翻译

题意简述

Takahashi 和 Aoki 正在竞选。

一共有 $n(1\le n\le 100)$ 个选区，每个选区有 $x_i(1\le x_i\le 10^9)$ 个选民支持 Takahashi，$y_i(1\le y_i\le 10^9,x_i+y_i\equiv1\pmod2)$ 个选民支持 Aoki。

如果其中一人在这个选区的支持者比另一个人多，那么他将获得 $z_i(\sum^n_{i=1}z_i\le10^5,(\sum^n_{i=1}z_i)\equiv1\pmod2)$ 点威望。

最终威望值更大的人将竞选成功。

现在，因为 Takahashi 的支持者不够多。所以他想知道：至少还要多少个选民放弃支持 Aoki 而支持 Takahashi 他才能竞选成功。

题目描述

高橋君と青木君が選挙で戦っています。 選挙区は $N$ 個あります。$i$ 番目の選挙区には $X_i\ +\ Y_i$ 人の有権者がいて、そのうち $X_i$ 人が高橋派、$Y_i$ 人が青木派です。($X_i\ +\ Y_i$ はすべて奇数です) それぞれの区では、多数派がその区の $Z_i$ 議席を全て獲得します。そして、$N$ 個の選挙区全体として過半数の議席を獲得した方が選挙に勝利します。($\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

1
3 8 1

样例输出 #1

3

样例 #2

样例输入 #2

2
3 6 2
1 8 5

样例输出 #2

4

样例 #3

样例输入 #3

3
3 4 2
1 2 3
7 2 6

样例输出 #3

0

样例 #4

样例输入 #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

提示

制約

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

Sample Explanation 1

選挙区が $1$ 個しかないので、$1$ 番目の選挙区で議席を獲得した人が選挙に勝利します。 $1$ 番目の選挙区の青木派 $3$ 人を高橋派に鞍替えさせると、$1$ 番目の選挙区にいる有権者のうち高橋派は $6$ 人、青木派は $5$ 人になり、高橋君は議席を獲得できます。

Sample Explanation 2

$1$ 番目の選挙区の議席数よりも $2$ 番目の選挙区の議席数の方が多いため、高橋君が選挙に勝つには $2$ 番目の選挙区で高橋派を多数派にする必要があります。 $2$ 番目の選挙区の青木派の $4$ 人を鞍替えさせると高橋君は $5$ 議席を獲得できます。このとき青木君の獲得する議席は $2$ 議席なので、高橋君は選挙に勝利できます。

Sample Explanation 3

青木派から高橋派に鞍替えする人が $0$ 人でも高橋君が選挙で勝つ場合は $0$ 人が答えになります。