#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

typedef long long ll;

int n, k;
ll w[15], h[15], q[15];

ll waste[1 << 15];
ll memo[1 << 15][16];

const ll MOD = 1000000007;

void comp_waste()
{
  waste[0] = 0;
  for (ll mask = 1; mask < (1 << n); mask++) {
    ll W = 0, H = 0;
    for (int i = 0; i < n; i++) {
      if (mask & (1 << i)) {
	W = max(W, w[i]);
	H = max(H, h[i]);
      }
    }
    waste[mask] = 0;
    for (int i = 0; i < n; i++) {
      if (mask & (1 << i)) {
	waste[mask] += q[i] * (W*H - w[i]*h[i]);
      }
    }
  }
}

ll f(ll mask, int k)
{
  if (memo[mask][k] >= 0)
    return memo[mask][k];
  
  if (k == 1 || mask == 0) {
    return memo[mask][k] = waste[mask];
  }

  // now try all nonempty subsets for one envelope
  ll ans = LLONG_MAX;
  for (ll subset = mask; subset > 0; subset = (subset-1) & mask) {
    ans = min(ans, waste[subset] + f(mask-subset, k-1));
  }

  return memo[mask][k] = ans;
}

int main()
{
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> w[i] >> h[i] >> q[i];
  }

  for (int i = 0; i < (1 << n); i++) {
    fill(memo[i], memo[i]+k+1, -1);
  }
  comp_waste();
  
  cout << f((1 << n)-1, k) << endl;

  return 0;
}