27 (макс сумма не кратная k)

#https://inf-ege.sdamgia.ru/problem?id=27424
def gen_pairs(previous, pair):
    ret = []
    for lst in previous:
        if lst == 0:
            continue
        for cur in pair:
            ret.append(lst + cur)
    return ret


data = open('27.txt').readlines()
n = int(data[0])
k = 3 #!!!!!!!!!!!!!!
a = data[1:]
for i in range(n):
    a[i] = list(map(int, a[i].split()))
dp = [[0 for i in range(k)] for j in range(n)]
for x in a[0]:
    dp[0][x % k] = max(dp[0][x % k], x)
for i in range(1, n):
    for sum in gen_pairs(dp[i - 1], a[i]):
        dp[i][sum % k] = max(dp[i][sum % k], sum)
print(max(dp[-1][1:]))