축하 카드 봉투

카드 회사는 크기가 제각각인 축하 카드를 만든다. 디자이너마다 원하는 치수가 달라 카드 종류가 많고, 종류마다 만들어야 하는 수량이 정해져 있다.

이 카드에 쓸 봉투를 주문해야 한다. 주문할 수 있는 봉투 크기의 가짓수에는 상한이 있고, 그 상한은 카드 크기의 가짓수보다 작을 수 있다. 모든 카드는 어떤 봉투엔가 들어가야 하며 공간이 남아도 된다. 이때 낭비되는 종이를 최소로 만들어야 한다. 낭비는 카드 한 장마다 봉투 넓이에서 카드 넓이를 뺀 값으로 잰다. 예를 들어 $10 \times 4$ 카드를 $10 \times 4$ 봉투에 넣으면 낭비가 없고, 같은 카드를 $12 \times 5$ 봉투에 넣으면 낭비가 $20$이다. 카드를 회전해서 넣을 수는 없다.

카드 종류가 다섯 가지라고 하자. $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 \times 10 = 44$, $144 - 9 \times 8 = 72$, $144 - 4 \times 12 = 96$, $144 - 12 \times 4 = 96$, $144 - 2 \times 3 = 138$이다. 전체 낭비는 $44 \times 5 + 72 \times 10 + 96 \times 20 + 96 \times 8 + 138 \times 16 = 5836$이다.

봉투를 두 종류 살 수 있다면 $10 \times 10$, $9 \times 8$, $12 \times 4$ 카드를 $12 \times 10$ 봉투에 넣고 $4 \times 12$, $2 \times 3$ 카드를 $4 \times 12$ 봉투에 넣는 것이 가장 좋다. 이때 낭비는 $1828$이다.

봉투를 다섯 종류 살 수 있다면 카드 종류마다 봉투를 하나씩 맞출 수 있으므로 낭비가 없다.

카드 종류 목록과 살 수 있는 봉투 종류의 최대 개수가 주어질 때, 낭비되는 종이의 최솟값을 구하라.

첫 줄에 정수 $n$과 $k$가 공백으로 구분되어 주어진다 ($1 \le n, k \le 15$). $n$은 카드 종류의 수, $k$는 주문할 수 있는 봉투 종류의 최대 개수다.

다음 $n$개의 줄에는 카드 한 종류를 나타내는 정수 $w$, $h$, $q$가 공백으로 구분되어 주어진다 ($1 \le w, h, q \le 10000$). $w$는 이 종류 카드의 가로 길이, $h$는 세로 길이, $q$는 수량이다.

낭비되는 종이 넓이의 최솟값을 정수 하나로 출력한다.