{"raw_statement":[{"iden":"problem statement","content":"Takahashi and Aoki are competing in an election.  \nThere 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.)  \nIn 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.)  \nAt least how many voters must switch from Aoki to Takahashi for Takahashi to win the election?"},{"iden":"constraints","content":"*   $1 \\leq N \\leq 100$\n*   $0 \\leq X_i, Y_i \\leq 10^9$\n*   $X_i + Y_i$ is odd.\n*   $1 \\leq Z_i$\n*   $\\displaystyle \\sum_{i=1}^N Z_i \\leq 10^5$\n*   $\\displaystyle \\sum_{i=1}^N Z_i$ is odd."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$X_1$ $Y_1$ $Z_1$\n$X_2$ $Y_2$ $Z_2$\n$\\vdots$\n$X_N$ $Y_N$ $Z_N$"},{"iden":"sample input 1","content":"1\n3 8 1"},{"iden":"sample output 1","content":"3\n\nSince there is only one district, whoever wins the seat in that district wins the election.  \nIf 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."},{"iden":"sample input 2","content":"2\n3 6 2\n1 8 5"},{"iden":"sample output 2","content":"4\n\nSince 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.  \nIf 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."},{"iden":"sample input 3","content":"3\n3 4 2\n1 2 3\n7 2 6"},{"iden":"sample output 3","content":"0\n\nIf Takahashi will win the election even if zero voters switch sides, the answer is $0$."},{"iden":"sample input 4","content":"10\n1878 2089 16\n1982 1769 13\n2148 1601 14\n2189 2362 15\n2268 2279 16\n2394 2841 18\n2926 2971 20\n3091 2146 20\n3878 4685 38\n4504 4617 29"},{"iden":"sample output 4","content":"86"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}