Задача "Нет Монет"

import itertools 
A = input().split('],[') 
g = [int(x) for x in A[0][1].split(',')] 
k = [int(x) for x in A[1].split(',')] 
cth = [int(x) for x in A[2][:-1].split(',')] 
 
sdacha_ = [] 
for i in range(1, len(k)+1): 
    sdacha = set(sum(_b) for _b in itertools.combinations(k, i)) 
    sdacha = list(sdacha) 
    sdacha_.extend(sdacha) 
 
gosha_ = [] 
for i in range(1, len(g)+1): 
    gosha = set(sum(_b) for _b in itertools.combinations(g, i)) 
    gosha = list(gosha) 
    gosha_.extend(gosha) 
    monet = sdacha_ + gosha_ 
 
sum_ = [sum(cth)] 
for i in range(1, len(cth)+1): 
    cloth = list(sum(_b) for _b in itertools.combinations(cth, i)) 
    cloth.sort(reverse=True) 
 
sum_i=[] 
for j in cloth: 
    sumx = sum(cth) - j 
    sum_i.append(sumx) 
    sum_.extend(sum_i) 
#Summa = 0 
cth.sort() 
gosha_.sort(reverse = True) 
G = 0 
if sum(g)< cth[0]: 
    Summa ==0 
else: 
    for i in range(0,len(sum_)): 
        for j in range(0,len(gosha_)): 
            S = gosha_[j] - sum_[i] 
        if S==0 and G==0: 
            Summa =sum_[i] 
            G=1 
        elif ((S>0) and (S in monet) and (G==0)): 
#print(sum_[i] , i) 
            Summa = sum_[i] 
            G=1 
 
print(Summa)

import itertools 
import re
 
t = '[7, 9, 9, 8, 7],[7, 8, 9, 8, 9],[8, 8, 6, 2, 4, 3]'
# A = input('>> ')[1:-1].split('],[')
A = t[1:-1].split('],[')
 
gosha_money = [int(item) for item in re.compile('\d+').findall(A[0])]
gosha_money.sort()
 
kassir_money = [int(item) for item in re.compile('\d+').findall(A[1])]
kassir_money.sort()
 
cost_cloths = [int(item) for item in re.compile('\d+').findall(A[2])]
cost_cloths.sort()
 
def sums(lis):
    tmp = []
    for L in range(0, len(lis)+1):
        for subset in itertools.combinations(lis, L):
            tmp.append(sum(subset))
    return tmp
 
sum_g_m = sums(gosha_money)
sum_c_c = sums(cost_cloths)
sum_k_m = sums(kassir_money)
sum_g_m.sort(reverse=True)
sum_c_c.sort(reverse=True)
 
def main():
    def check(check_var):
        if item in sum_k_m:
            return True
        else:
            return False
 
    check_var = 0
    for item in sum_g_m:
        for item_2 in sum_c_c:
            if item - item_2 > 0:
                check_var = item - item_2
                if check(check_var) == True:
                    return item_2
                    break
print(main())

s = eval('[7, 9, 9, 8, 7],[7, 8, 9, 8, 9],[8, 8, 6, 2, 4, 3]')
G = sorted(s[0])
K = sorted(s[1])
O = sorted(s[2])