Набор данных состоит из n пар натуральных чисел. Необходимо выбрать из каждой пары одно число так, чтобы сумма выбранных чисел была максимально возможной и не делилась на 5, при этом сумма невыбранных чисел не делилась на 3.
Какую наибольшую сумму выбранных чисел можно при этом получить?
Формат входных данных
Набор данных состоит из пар натуральных чисел.
Первая строка входных данных содержит число n — количество строк, 
. Следующие n строк содержат пару натуральных чисел не превышающие 
.
Формат выходных данных
Программа должна вывести целое число — максимальную сумму.
Пример:
Ответом для примера будет: 
Метод наименьших разностей
f = open(’22.txt’)
n = int(f.readline())
mr = [10 ** 10] * (3 * 5) # Список для хранения минимальных разностей по остаткам
maxS = 0 # Сумма выбранных чисел
minS = 0 # Сумма невыбранных чисел
for i in range(n):
a, b = map(int, f.readline().split()) # Считываем числа
maxS += max(a, b) # Прибавляем к сумме максимальное число из пары
minS += min(a, b) # Прибавляем к сумме минимальное число из пары
r = abs(a - b) # Разность между элементами
mr1 = mr[:] # Создаём копию списка разностей
for j in range(15):
# Ищем минимальную сумму нескольких разностей
if r + mr1[j] < mr[(r + mr1[j]) % 15]:
mr[(r + mr1[j]) % 15] = r + mr1[j]
# Если текущая разность меньше разности в списке
if r < mr[r % 15]:
mr[r % 15] = r
# Обе суммы не удовлетворяют условию
if maxS % 5 == 0 and minS % 3 == 0:
# Находим среди минимальных разностей по остаткам такую минимальную разность,
# которая не будет кратна ни 3, ни 5, чтобы поменять остаток обеих сумм
d = min(mr[j] for j in range(15) if (mr[j] % 5 != 0) and (mr[j] % 3 != 0))
# Отнимаем разность от максимальной суммы и прибавляем к минимальной
maxS -= d
minS += d
# Сумма невыбранных чисел не удовлетворяет условию
elif maxS % 5 != 0 and minS % 3 == 0:
# Остаток для максимальной суммы, вычитание которого даст кратность 5
ost5 = maxS % 5
# Находим среди минимальных разностей по остаткам такую минимальную разность,
# которая не будет кратна 3, чтобы поменять остаток минимальной суммы,
# и при этом остаток которой не будет равен ost5, чтобы не сделать макс. сумму кратной 5
d = min(mr[j] for j in range(15) if (mr[j] % 5 != ost5) and (mr[j] % 3 != 0))
# Отнимаем разность от максимальной суммы и прибавляем к минимальной
maxS -= d
minS += d
# Сумма выбранных чисел не удовлетворяет условию
elif maxS % 5 == 0 and minS % 3 != 0:
# Остаток для минимальной суммы, прибавление которого даст кратность 3
ost3 = 3 - minS % 3
# Находим среди минимальных разностей по остаткам такую минимальную разность,
# которая не будет кратна 5, чтобы поменять остаток максимальной суммы,
# и при этом остаток которой не будет равен ost3, чтобы не сделать мин. сумму кратной 3
d = min(mr[j] for j in range(15) if (mr[j] % 5 != 0) and (mr[j] % 3 != ost3))
# Отнимаем разность от максимальной суммы и прибавляем к минимальной
maxS -= d
minS += d
print(maxS) # Выводим итоговую сумму выбранных чисел
Метод частичных сумм
#Для решения задачи будем искать макс. суммы с остатками по модулю 5
#и смотреть на их остатки по модулю 3 -
#чтобы сравнить с остатком суммы всех чисел.
#Если окажется, что эти остатки равны, то сумма нам не подходит
#(так как тогда (sum_all - current_sum) % 3 == 0, и надо смотреть на другую.
#Поэтому надо собрать суммы с разными парами остатков по модулю 5 и 3,
#а все такие суммы будут иметь разные остатки по модулю 3*5 = 15
modul = 15
def fun(a, a_new, x):
for j in range(modul):
k = (a[j] + x) % modul
a_new[k] = max(a_new[k], a[j] + x)
a = [0] * modul
n = int(input())
sum_all = 0
for i in range(n):
x, y = map(int, input().split())
a_new = [-100000000] * modul
fun(a, a_new, x)
fun(a, a_new, y)
sum_all += x + y
a = a_new[:]
print(max([i for i in a if (i % 5 != 0 and i % 3 != sum_all % 3)]))