Задача
Mamãe e papai decidiram que queriam agradar as crianças com doces. Além disso, eles querem treiná-los em matemática. Eles escreveram vários pares de números em um pedaço de papel (o número de pares é ímpar) e definiram as regras para escolher o número de doces:
- para que os pais saibam quanto precisam para comprar doces, as crianças escolhem a quantidade de doces com vários dias de antecedência (para tantos dias quantos pares de números escritos em um pedaço de papel);
- de cada par de números, as crianças podem escolher exatamente um número para que a paridade da soma dos números selecionados coincida com a paridade da maioria dos números selecionados;
- as crianças devem escolher os números de forma a comer o mínimo possível de doces (afinal, os pais se preocupam com a saúde dos filhos).
Determine o número mínimo de doces que os pais precisam comprar com essa escolha.
É garantido que tal escolha é possível.
Você recebe dois arquivos, cada um com a seguinte estrutura:
- a primeira linha contém o número
N - número total de pares (número ímpar);
- cada uma das seguintes
N linhas contém dois números.
Todos os números são naturais, não excedendo 10000.
Exemplos
| # |
Entrada |
Resposta |
| 1 |
3
10 5
34
1 2
| 9 |
Em sua resposta, indique o número de doces encontrado primeiro para arquivo 1, depois para arquivo 2. Separe os números entre si com ponto e vírgula, sem espaços. Por exemplo: 123;456.