#include <bits/stdc++.h>
using namespace std;
struct Books {
  int T, A, B;
};
long solve(Books *arr, int m, int n, int s, vector<vector<vector<long>>> &dp) {
  if (s == 0) {
    if (m == 0 && n == 0) {
      dp[m][n][s] = 0;
      return 0;
    } else {
      dp[m][n][s] = INT_MAX;
      return INT_MAX;
    }
  }
  if (m == 0 && n == 0) {
    dp[m][n][s] = 0;
    return 0;
  }
  if (dp[m][n][s] != -1) {
    return dp[m][n][s];
  }
  long ans;
  if (arr[0].A == 0 && arr[0].B == 0) {
    ans = solve(arr + 1, m, n, s - 1, dp);
  } else {
    if (solve(arr + 1, max(0, m - arr[0].A), max(0, n - arr[0].B), s - 1, dp) ==
        INT_MAX) {
      ans = solve(arr + 1, m, n, s - 1, dp);
    } else {
      if (solve(arr + 1, m, n, s - 1, dp) == INT_MAX) {
        ans = arr[0].T + solve(arr + 1, max(0, m - arr[0].A),
                               max(0, n - arr[0].B), s - 1, dp);
      } else {
        ans = min(solve(arr + 1, m, n, s - 1, dp),
                  arr[0].T + solve(arr + 1, max(0, m - arr[0].A),
                                   max(0, n - arr[0].B), s - 1, dp));
      }
    }
  }
  dp[m][n][s] = ans;
  return dp[m][n][s];
}
int main() {
  int n, k;
  cin >> n >> k;
  Books *arr = new Books[n];
  for (int i = 0; i < n; i++) {
    int t, a, b;
    cin >> t >> a >> b;
    arr[i].T = t;
    arr[i].A = a;
    arr[i].B = b;
  }
  vector<vector<vector<long>>> dp(
      k + 1, vector<vector<long>>(k + 1, vector<long>(n + 1, -1)));
  long ans = solve(arr, k, k, n, dp);
  if (ans == 1000000000000000) {
    cout << -1;
  } else {
    cout << ans;
  }
  return 0;
}
