Задача
Mom and dad decided that they wanted to please the children with sweets. In addition, they want to train them in mathematics. They wrote several pairs of numbers on a piece of paper (the number of pairs is odd) and set the rules for choosing the number of sweets:
- so that parents know how much they need to buy sweets, children choose the number of sweets for several days in advance (for as many days as there are pairs of numbers written on a piece of paper);
- from each pair of numbers, children can choose exactly one number so that the parity of the sum of the selected numbers coincides with the parity of the majority of the selected numbers;
- children should choose the numbers in such a way as to eat as few sweets as possible (after all, parents care about the health of their children).
Determine the minimum number of sweets that parents need to buy with this choice.
It is guaranteed that such a choice is possible.
You are given two files, each with the following structure:
- first line contains number
N - total number of pairs (odd number);
- each of the following
N lines contains two numbers.
All numbers are natural, not exceeding 10000.
Examples
| # |
Input |
Answer |
| 1 |
3
10 5
34
1 2
| 9 |
In your answer, indicate the found number of sweets first for file 1, then for file 2. Separate numbers from each other with a semicolon, without spaces. For example: 123;456.