您的贺卡公司制作独特的贺卡。由于卡片设计师的奇思妙想，这些贺卡的尺寸各不相同。卡片种类繁多，每种卡片都有您需要制造的具体数量。

您的工作是确定为这些贺卡订购哪些信封。您对可以订购的不同尺寸的信封数量有严格的限制，该数量可能少于不同尺寸卡片的数量。您需要准备信封，使得每张卡片都能装入某个信封中（可能留有空余空间），并使浪费的纸张量最小化。对于每张卡片，浪费的纸张量定义为信封面积减去卡片面积的差值。例如，一张 $10 \times 4$ 的卡片装入 $10 \times 4$ 的信封中没有纸张浪费，但一张 $10 \times 4$ 的卡片装入 $12 \times 5$ 的信封中会有 $20$ 的浪费。您不得旋转卡片以使其更好地放入信封。

假设您有 $5$ 种卡片：$10 \times 10$（$5$ 张）、$9 \times 8$（$10$ 张）、$4 \times 12$（$20$ 张）、$12 \times 4$（$8$ 张）和 $2 \times 3$（$16$ 张）。

现在，假设您只能购买一种类型的信封。由于所有卡片都必须装入该尺寸的信封中，您能使用的最小信封尺寸是 $12 \times 12$，面积为 $144$。每种卡片造成的浪费分别为 $144 - 10 \cdot 10 = 44$，$144 - 9 \cdot 8 = 72$，$144 - 4 \cdot 12 = 96$，$144 - 12 \cdot 4 = 96$ 以及 $144 - 2 \cdot 3 = 138$。总浪费为 $44 \cdot 5 + 72 \cdot 10 + 96 \cdot 20 + 96 \cdot 8 + 138 \cdot 16 = 5836$。

假设您可以购买 $2$ 种类型的信封。最好的做法是将 $10 \times 10$、$9 \times 8$ 和 $12 \times 4$ 的卡片放入 $12 \times 10$ 的信封中，将 $4 \times 12$ 和 $2 \times 3$ 的卡片放入 $4 \times 12$ 的信封中。这加起来的浪费为 $1828$。

如果您可以购买 $5$ 种类型的信封，那么您可以为每种卡片匹配一种信封类型，这样就不会有浪费！

给定卡片类型列表和您可以购买的信封类型数量，您能实现的最小纸张浪费量是多少？

输入格式

每个输入包含一个测试用例。请注意，您的程序可能会在不同的输入上多次运行。输入的第一行包含两个空格分隔的整数 $n$ 和 $k$ ($1 \le n, k \le 15$)，其中 $n$ 是不同卡片类型的数量，$k$ 是您可以订购的最大信封类型数量。接下来的 $n$ 行，每行包含三个整数，描述一种卡片类型。这些整数分别是 $w$、$h$ 和 $q$ ($1 \le w, h, q \le 10,000$)，其中 $w$ 是该类型卡片的宽度，$h$ 是高度，$q$ 是该类型卡片的数量。

输出格式

输出一个整数，表示可能产生的最小纸张浪费总量。

样例

样例输入 1

5 1
10 10 5
9 8 10
4 12 20
12 4 8
2 3 16

样例输出 1

5836

样例输入 2

5 2
10 10 5
9 8 10
4 12 20
12 4 8
2 3 16

样例输出 2

1828

样例输入 3

5 5
10 10 5
9 8 10
4 12 20
12 4 8
2 3 16

样例输出 3

0