#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll cost[1 << 15];
ll dp[16][1 << 15];
ll w[15], h[15];
ll q[15];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> h[i] >> q[i];
    }
    for (int s = 0; s < (1 << n); s++) {
        ll maxh = 0;
        ll maxw = 0;
        for (int i = 0; i < n; i++) {
            if ((s >> i) & 1) {
                maxh = max(maxh, h[i]);
                maxw = max(maxw, w[i]);
            }
        }
        for (int i = 0; i < n; i++) {
            if ((s >> i) & 1) {
                cost[s] +=  q[i] * (maxh * maxw - h[i] * w[i]);
            }
        }
    }
    dp[0][0] = 0;
    for (int s = 1; s < (1 << n); s++) {
        dp[0][s] = 1ll << 50;
    }
    for (int i = 1; i <= k; i++) {
        for (int s = 0; s < (1 << n); s++) {
            dp[i][s] = min(dp[i-1][s], cost[s]);
            for (int s1 = s-1; s1; s1 = s & (s1 - 1)) {
                dp[i][s] = min(dp[i][s], dp[i-1][s1] + cost[s1 ^ s]);
            }
        }
    }
    cout << dp[k][(1 << n) - 1] << endl;
}