题目背景

有 $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$ 种信件都放进去。 问，如何设计信封能够使得浪费的总面积最小？ 输出最小浪费总面积。

输入格式

第一行输入两个整数 $n,k$ ，表示信件种数和信封种数。

接下来 $n$ 行，每行三个整数 $a_i,b_i,c_i$, 表示一种信件的长，宽以及个数。

输出格式

输出一个整数，表示最少浪费的空间大小。

输入输出样例 #1

输入 #1

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

输出 #1

5836

输入输出样例 #2

输入 #2

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

输出 #2

1828

输入输出样例 #3

输入 #3

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

输出 #3

0

说明/提示

$1\le k\le n\le 15$

$1\le a_i,b_i,c_i \le 10000$