U527234 # 设计信封

有 $n$ 种信件：长 $a_i$，宽 $b_i$，个数 $c_i$ 。需要制作 $k$ 种信封，长 $A_i$ ,宽 $B_i$ 。最少浪费多少空间？

一共 $n$ 种信件，每种信件有属性 $a_i,b_i,c_i$ 分别表示 长宽和个数。 现在有 $k$ 次设计信封的机会，每种信封也有长和宽，仅当信封的长和宽都分别大于等于信件的长和宽时，信件才能放到信封中，放置方向是固定的。 如果信件尺寸为 $a$ 和 $b$ ，信封尺寸为 $A$ 和 $B$ 满足 $a \le A,\ b \le B $,则信件可以放进该信封，且浪费的面积为 $A \times B − a \times b$ 。 要设计出最多 $k$ 种信封将 $n$ 种信件都放进去。 问，如何设计信封能够使得浪费的总面积最小？ 输出最小浪费总面积。

无

无

$1\le k\le n\le 15$ $1\le a_i,b_i,c_i \le 10000$