#include <bits/stdc++.h>

using namespace std;

struct node {
	int tag, exp, val;
}a[100010];

int f[1010][1010];

int __[4] = {0, 520, 1314, 1024};

int main()
{
	int N, K;
	while (scanf("%d%d", &N, &K) != EOF) {
		for (int i = 0; i < N; i++) {
			scanf("%d%d%d", &a[i].tag, &a[i].exp, &a[i].val);
		}
		sort(a, a + N, [](const node &a, const node &b) {
			if (a.exp != b.exp) return a.exp < b.exp;
			return __[a.tag] > __[b.tag];
			});
		memset(f, 0x3f, sizeof(f));
		f[0][0] = 0;
		for (int i = 0; i < N; i++) {
			for (int x = K; x >= 0; x--) {
				for (int y = K; y >= 0; y--) {
					if (a[i].tag == 1 || a[i].tag == 3) {
						if (x + 1 <= y) {
							f[x + 1][y] = min(f[x + 1][y], f[x][y] + a[i].val);
						}
					}
					if (a[i].tag == 2 || a[i].tag == 3) {
						if (y + 1 <= K) {
							f[x][y + 1] = min(f[x][y + 1], f[x][y] + a[i].val);
						}
					}
				}
			}
		}
		printf("%d\n", f[K][K]);
	}
	return 0;
}