Решение статикой.

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

Дифф — обозначение для какой-то разницы, от слова difference.

Итак, казалось бы все просто — можно добавить мин. дифф с остатком 1. Но на самом деле этого недостаточно. Ведь еще можно добавить к подобной сумме два мин. диффа с остатком 2. И ведь действительно: S(2) + diff(1) = (0) или S(2) + diff(2) + post_diff(2) = (0). (добавляем, так как уже посчитали минимальную сумму, теперь ее можно только увеличивать). Тоже самое и для суммы, с остатком 1.

Собственно, нужно хранить четыре разности: первые две с остатком 1, вторые с остатком 2.

    f = open(’A5-8.txt’)
    n = int(f.readline())
    ans = 0
    #индексы 0 и 1 отвечают за мин дифы с ост. 1
    #2 и 3 за мин дифы с ост. 2
    diff = [1000000]*4
    for i in range(n):
        a, b = map(int, f.readline().split())
        ans += min(a,b)
        tmp = abs(a-b)
        if tmp % 3 == 1:
            if tmp < diff[0]:
                diff[1], diff[0] = diff[0], tmp
            else:
                diff[1] = min(diff[1], tmp)
        if tmp % 3 == 2:
            if tmp < diff[2]:
                diff[3], diff[2] = diff[2], tmp
            else:
                diff[3] = min(diff[3], tmp)

    if ans % 3 == 0:
        print(ans)
    elif ans % 3 == 1:
        print(ans + min(diff[2], diff[0]+diff[1]))
    else:
        print(ans + min(diff[0], diff[2] + diff[3]))