题目描述

你的贺卡公司生产独特的贺卡。由于贺卡设计师的奇思妙想，这些贺卡的尺寸差异很大。贺卡有很多不同的类型，每种类型都有需要生产的具体数量。

你的任务是确定为这些贺卡订购什么样的信封。你对信封尺寸的种类数有严格的限制，该限制可能少于贺卡尺寸的种类数。你需要订购信封，使得每张贺卡都能装入某种信封（允许有多余空间），并使得浪费的纸张最小化。浪费的纸张按每张贺卡信封面积超出贺卡面积的部分计算。例如，一张 $10 \times 4$ 的贺卡放入 $10 \times 4$ 的信封中，浪费为 $0$；而放入 $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 \leq n, k \leq 15$），其中 $n$ 是贺卡的不同类型数量，$k$ 是你能订购的最大信封类型数量。接下来的 $n$ 行，每行包含三个整数，描述一种贺卡类型。这三个整数是 $w$、$h$ 和 $q$（$1 \leq w, h, q \leq 10{,}000$），其中 $w$ 是该类型贺卡的宽度，$h$ 是高度，$q$ 是该类型贺卡的数量。

输出格式

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

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

5836

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

1828

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

0

提示

翻译由 DeepSeek V3.2 完成