В текстовом файле записан набор пар натуральных чисел, не превышающих 
. Необходимо выбрать из набора некоторые пары так, чтобы первое число в каждой выбранной паре было нечётным, сумма бОльших чисел во всех выбранных парах была нечётной, а сумма меньших — чётной. Какую наибольшую сумму чисел во всех выбранных парах можно при этом получить?
Пример входных данных:
Ответ для данного примера: 
Будем собирать максимальную сумму, а потом посмотрим, что получится с остатками.
Если все хорошо, то так и выведем. Если где-то нарушена четность — заводим специальную переменную,
отвечающую за минимальную сумму в паре с определенными остатками:
- у наибольшего числа 0, у меньшего — 1;
- у наибольшего 1, у меньшего — 0;
- оба числа нечетные.
Останется тогда из суммы с неверным остатком (возможно из обеих) вычесть нужную комбинацию минимальных сумм.
f = open(’21.txt’)
n = int(f.readline())
sMax = 0
sMin = 0
md01 = 10000000000000000
md10 = 10000000000000000
md11 = 10000000000000000
for i in range(n):
x, y = map(int, f.readline().split())
if x % 2 == 1:
maxim = max(x, y)
minim = min(x, y)
sMax += maxim
sMin += minim
if maxim % 2 == 0 and minim % 2 == 1:
md01 = min(md01, x + y)
if maxim % 2 == 1 and minim % 2 == 0:
md10 = min(md10, x + y)
if maxim % 2 == 1 and minim % 2 == 1:
md11 = min(md11, x + y)
if sMax % 2 == 1 and sMin % 2 == 0:
print(sMax + sMin)
elif sMax % 2 == 1 and sMin % 2 == 1:
# Обратим внимание, что остатки 01 может иметь
# как пара с соответствующими остатками,
# так и две пары с остатками 10 и 11. Учтем это
print(sMax + sMin - min(md01, md10 + md11))
elif sMax % 2 == 0 and sMin % 2 == 0:
# Аналогично 10 = 11 + 01
print(sMax + sMin - min(md10, md11 + md01))
elif sMax % 2 == 0 and sMin % 2 == 1:
# Аналогично 11 = 10 + 01
print(sMax + sMin - min(md11, md10 + md01))