Сумма чисел, не делящаяся на три (из ЕГЭ)

[ViktorR]

Есть задача из сборника по ЕГЭ.

Имеется набор данных (файл), состоящий из пар положительных целых чисел.
Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной.
Гарантируется, что искомую сумму получить можно.

В первой строке количество пар N (1 ≤ N ≤ 100000).
Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
6
1 3
5 12
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 32.

Перебирать разные варианты не рекомендуется из-за возможного большого числа входных данных.
Не могу сообразить, какой алгоритм можно придумать.
Например, можно было бы создать очередь на некоторое небольшое число таких пар.
В начале просто выбираем максимальный элемент и суммируем. В конце проверяем делимость суммы на три и если делится, то рассматриваем (перебираем) элементы, которые сохранились в очереди.
Но какой размер очереди будет гарантировать нормальную работу алгоритма???

Поделитесь, пожалуйста, алгоритмом или ссылкой на что либо подобное.

[ViktorR]

Решение найдено.
1. Считываем очередную пару
2. Максимальное число из пары добавляем в сумму
3. Вычисляем разность в паре и проверяем эту разность на кратность тройке. Если некратна, то:
- при первом обнаружении сохраняем и корректируем флажок.
- при повторном обнаружении такой разности, сохраняем минимальную.
4. Проверяем сумму на кратность 3
5. Если сумма делится, то корректируем (заменяем ранее добавленное число, при условии, что подходящая разность пар была найдена) на найденную минимальную разность, а иначе просто выводим вычисленное значение.
6. Если в наборе данных нет пар, разность которых некратно 3, а сумма кратна 3, то выводим 0.

# В алгоритме нет ограничения на максимальное число в исходных данных
flag = False                          # полагаем, что разность пар кратна 3
fh = open('27-B.txt', 'r')            # Открываем файл на чтение (файлы прилагаются к заданию)
N = int(fh.readline())                # Число записей
print('N = ', N)
s = 0                                 # Начальное значение суммы
for i in range(N):                    # Для всех пар
    a, b = fh.readline().split()
    a = int(a); b = int(b)
    Max, Min = max(a, b), min(a, b)   # Сортируем пару
    D = Max - Min                     # Текущая разность
    s = s + Max                       # Увеличиваем сумму
    if (D % 3 > 0):                   # Разность пары не кратна 3
        if not flag:                  # Найдена первая подходящая разность
            D_min = D
            flag = True
        elif D_min > D:               # Минимальная разность, не кратная 3
            D_min = D

if (s % 3 == 0):                      # Сумма кратна 3
    if flag:                          # Есть пара, разность в которой не кратна 3
        s = s - D_min                 # Корректируем сумму
    else:                             # Для всех пар разность кратна 3
        s = 0
print(s)

PS: Это не моё решение. Нашёл на сайте (алгоритм рассмотрен более подробно):
https://inf-ege.sdamgia.ru/problem?id=11363

К сожалению поиск выдавал либо правила кратности, либо всё что есть в Сети о ЕГЭ.
Наконец то угадал форму запроса: "сумма пар не кратная 3 (ЕГЭ информатика)" и попал на подходящие сайты.