President

AtCoder

IDabc317_d

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

1
3 8 1

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.

Input #2

2
3 6 2
1 8 5

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.

Input #3

Output #3

0

If Takahashi will win the election even if zero voters switch sides, the answer is $0$.

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

Output #4

API Response (JSON)

{
  "problem": {
    "name": "President",
    "description": {
      "content": "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$",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc317_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments