Greeting Card Envelopes

Your greeting card company makes cards in many different sizes. The designers pick whatever dimensions they like, so there are many card types, and each type has a quantity you must manufacture.

You have to order envelopes for these cards. There is a hard limit on how many different envelope sizes you may order, and that limit can be smaller than the number of distinct card sizes. Every card has to fit inside some envelope, possibly with room to spare, and the wasted paper must be as small as possible. Waste is measured per card as the area of the envelope minus the area of the card. A $10 \times 4$ card in a $10 \times 4$ envelope wastes nothing, while the same card in a $12 \times 5$ envelope wastes $20$. You may not rotate a card to make it fit.

Suppose you have five card types: $10 \times 10$ (5 cards), $9 \times 8$ (10 cards), $4 \times 12$ (20 cards), $12 \times 4$ (8 cards), and $2 \times 3$ (16 cards).

If you can buy only one envelope type, every card has to fit in it, so the smallest usable envelope is $12 \times 12$ with area $144$. The waste per card type is $144 - 10 \times 10 = 44$, $144 - 9 \times 8 = 72$, $144 - 4 \times 12 = 96$, $144 - 12 \times 4 = 96$, and $144 - 2 \times 3 = 138$. The total waste is $44 \times 5 + 72 \times 10 + 96 \times 20 + 96 \times 8 + 138 \times 16 = 5836$.

If you can buy two envelope types, the best choice puts the $10 \times 10$, $9 \times 8$, and $12 \times 4$ cards in $12 \times 10$ envelopes and the $4 \times 12$ and $2 \times 3$ cards in $4 \times 12$ envelopes, for a total waste of $1828$.

If you can buy five envelope types, you can match one envelope to each card type and waste nothing.

Given the list of card types and the number of envelope types you may buy, find the smallest possible amount of wasted paper.

The first line contains two space separated integers $n$ and $k$ ($1 \le n, k \le 15$), where $n$ is the number of card types and $k$ is the maximum number of envelope types you may order.

Each of the next $n$ lines contains three space separated integers $w$, $h$, and $q$ ($1 \le w, h, q \le 10000$) describing one card type: $w$ is the width of these cards, $h$ is the height, and $q$ is the quantity.

Print a single integer, the smallest possible total area of wasted paper.