Everything is great about Ilya's city, except the roads. The thing is, the only ZooVille road is represented as *n* holes in a row. We will consider the holes numbered from 1 to *n*, from left to right.

Ilya is really keep on helping his city. So, he wants to fix at least *k* holes (perharps he can fix more) on a single ZooVille road. 

The city has *m* building companies, the *i*-th company needs *c*<sub class="lower-index">*i*</sub> money units to fix a road segment containing holes with numbers of at least *l*<sub class="lower-index">*i*</sub> and at most *r*<sub class="lower-index">*i*</sub>. The companies in ZooVille are very greedy, so, if they fix a segment containing some already fixed holes, they do not decrease the price for fixing the segment. 

Determine the minimum money Ilya will need to fix at least *k* holes.
The first line contains three integers *n*, *m*, *k* (1 ≤ *n* ≤ 300, 1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>, 1 ≤ *k* ≤ *n*). The next *m* lines contain the companies' description. The *i*-th line contains three integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>, *c*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*, 1 ≤ *c*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>).
def main():
    n, m, k = list(map(int, input().split()))
    d = {i:[] for i in range(n+1)}
    inf = 100000000000
    for i in range(m):
        l, r, c = list(map(int, input().split()))
        d[l-1].append([r-1, c])

    dp = [[inf for i in range(n)] for i in range(n+1)]
    for i in range(n):
        dp[0][i] = 0

    for i in range(0, n+1):
        for j in range(0, n, 1):
            for curr in d[j]:
                r, c = curr[0], curr[1]
                if j != 0:
                    dp[i][j] = min(dp[i][j-1], dp[i][j])
                if i + r - j + 1 <= n:
                    for z in range(1, r - j + 2, 1):
                        dp[i+z][r] = min(dp[i+z][r], dp[i][j] + c)
    ans = inf
    for i in range(k, n+1):
        ans = min(ans, min(dp[i]))
    if ans != inf:
        print(ans)
    else:
        print(-1)
    

if __name__ == "__main__":
    main()
