input = [(1, 5, 10, 'a'), (2, 6, 20, 'b'), (3, 10, 70, 'c'), (5, 12, 30, 'd'), (7, 15,50, 'e'),
             (13, 17, 10, 'f'), (15, 20, 30, 'g'), (14, 25, 40, 'h'), (18, 26, 20, 'i')]

input = sorted(input, key=lambda tup: tup[1])

def find_interval(input, ith):
    if(ith == 0):
        return input[0][2]
    else:
        overlap = findOverlap(input, ith)
        print(overlap, ith)
        answer = []
        for k in overlap:
            answer.append(find_interval(input, k))
        return input[ith-1][2] + min(answer)#min(find_interval(input, j) for j in overlap)



def findOverlap(input, ith):
    overlap = []
    counter = ith-1
    for k in reversed(range(ith-1)):
        if(input[k][1]  >= input[ith-1][0]):
            overlap.append(counter)
            counter = counter - 1
    #print(ith, overlap)
    return overlap


print(find_interval(input, 9))