#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
int* initdkntor(int n, int * brokens, int m)
{
int * p = (int *)malloc(sizeof(int) * n);
memset(p, 0, sizeof(int) * n);
for (int i = 0; i < m; i++)
{
for (int j = brokens[i * 2] - 1; j < brokens[i * 2 + 1]; j++)
p[j] = 1;
}
return p;
}
int* tryit(int *seed, int n, int a, int b)
{
int * p = (int *)malloc(sizeof(int) * n);
memcpy(p, seed, sizeof(int) * n);
for (int i = a - 1; i < b; i++) p[i] = 0;
return p;
}
int check(int *p, int n)
{
for (int i = 0; i < n; i++) if (p[i]) return 1;
return 0;
}
int solve(int *seed, int seedcost, int n, int *sp, int spn)
{
if (!check(seed, n)) return seedcost;
if (!spn) return -1;
int min = -1;
for (int i = 0; i < spn; i++)
{
int * seed1 = tryit(seed, n, sp[i*3], sp[i*3+1]);
int cost = solve(seed1, seedcost + sp[i*3+2], n, sp + 3 * (i+1), spn - i-1);
if (cost != -1)
if (cost < min || min == -1) min = cost;
}
return min;
}
int main()
{
int s;
int n;
int m;
cin >> n >> m >> s;
int * bk = new int[n * 2];
for (int i = 0; i < n; i++)
cin >> bk[i*2] >> bk[i*2+1];
int * sp = new int[m * 3];
for (int i = 0; i < m; i++)
cin >> sp[i*3] >> sp[i*3+1] >> sp[i*3+2];
int * dkntor = initdkntor(s, bk, n);
int result = solve(dkntor, 0, s, sp, m);
cout << result << endl;
return 0;
}
I2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8c3RyaW5nLmg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCogaW5pdGRrbnRvcihpbnQgbiwgaW50ICogYnJva2VucywgaW50IG0pCnsKCWludCAqIHAgPSAoaW50ICopbWFsbG9jKHNpemVvZihpbnQpICogbik7CgltZW1zZXQocCwgMCwgc2l6ZW9mKGludCkgKiBuKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKQoJewoJCWZvciAoaW50IGogPSBicm9rZW5zW2kgKiAyXSAtIDE7IGogPCBicm9rZW5zW2kgKiAyICsgMV07IGorKykKCQkJcFtqXSA9IDE7Cgl9CglyZXR1cm4gcDsKfQoKaW50KiB0cnlpdChpbnQgKnNlZWQsIGludCBuLCBpbnQgYSwgaW50IGIpCnsKCWludCAqIHAgPSAoaW50ICopbWFsbG9jKHNpemVvZihpbnQpICogbik7CgltZW1jcHkocCwgc2VlZCwgc2l6ZW9mKGludCkgKiBuKTsKCWZvciAoaW50IGkgPSBhIC0gMTsgaSA8IGI7IGkrKykgcFtpXSA9IDA7CglyZXR1cm4gcDsKfQoKaW50IGNoZWNrKGludCAqcCwgaW50IG4pCnsKCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSBpZiAocFtpXSkgcmV0dXJuIDE7CglyZXR1cm4gMDsKfQoKaW50IHNvbHZlKGludCAqc2VlZCwgaW50IHNlZWRjb3N0LCBpbnQgbiwgaW50ICpzcCwgaW50IHNwbikKewoJaWYgKCFjaGVjayhzZWVkLCBuKSkgcmV0dXJuIHNlZWRjb3N0OwoJaWYgKCFzcG4pIHJldHVybiAtMTsKCWludCBtaW4gPSAtMTsKCWZvciAoaW50IGkgPSAwOyBpIDwgc3BuOyBpKyspCgl7CgkJaW50ICogc2VlZDEgPSB0cnlpdChzZWVkLCBuLCBzcFtpKjNdLCBzcFtpKjMrMV0pOwoJCWludCBjb3N0ID0gc29sdmUoc2VlZDEsIHNlZWRjb3N0ICsgc3BbaSozKzJdLCBuLCBzcCArIDMgKiAoaSsxKSwgc3BuIC0gaS0xKTsKCQlpZiAoY29zdCAhPSAtMSkKCQkJaWYgKGNvc3QgPCBtaW4gfHwgbWluID09IC0xKSBtaW4gPSBjb3N0OwoJfQoJcmV0dXJuIG1pbjsKfQoKaW50IG1haW4oKQp7CglpbnQgczsKCWludCBuOwoJaW50IG07CgljaW4gPj4gbiA+PiBtID4+IHM7CglpbnQgKiBiayA9IG5ldyBpbnRbbiAqIDJdOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCgkJY2luID4+IGJrW2kqMl0gPj4gYmtbaSoyKzFdOwoJaW50ICogc3AgPSBuZXcgaW50W20gKiAzXTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKQoJCWNpbiA+PiBzcFtpKjNdID4+IHNwW2kqMysxXSA+PiBzcFtpKjMrMl07CglpbnQgKiBka250b3IgPSBpbml0ZGtudG9yKHMsIGJrLCBuKTsKCWludCByZXN1bHQgPSBzb2x2ZShka250b3IsIDAsIHMsIHNwLCBtKTsKCWNvdXQgPDwgcmVzdWx0IDw8IGVuZGw7CglyZXR1cm4gMDsKfQ==