최고의 커피 (Small)

혜인의 하루는 아침에 커피를 마시는 것으로 시작한다.

혜인에게는 $N$가지 종류의 커피가 있다. $i$번째 종류의 커피는 $c_i$잔 남아 있고, 오늘부터 세어 $t_i$일째에 유통기한이 끝난다. $i$번째 종류($1 \le i \le N$)의 커피를 한 잔 마실 때마다 만족도 $s_i$를 얻는다. 유통기한이 지난 커피는 마실 수 없다. 다만 $t_i$일째 당일에는 그 커피를 마실 수 있다. 예를 들어 $t_i = 1$이면 오늘 안에 마시거나 그 커피를 포기해야 한다.

혜인은 커피를 하루에 한 잔만, 그것도 아침에만 마신다. 마실 수 있는 커피가 하나도 없는 날에는 만족도를 얻지 못한다.

오늘부터 $K$일째까지 커피를 마셔서 얻을 수 있는 만족도 합의 최댓값을 구하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 커피 종류의 수 $N$과 날수 $K$가 공백 한 칸으로 구분되어 주어진다. 이어지는 $N$개의 줄에는 각 종류의 남은 잔 수, 유통기한, 만족도가 다음 형식으로 주어진다.

ci ti si

제약

• $1 \le T \le 100$
• $1 \le N \le 8$
• $1 \le K \le 8$
• $1 \le c_i \le K$
• $1 \le t_i \le K$
• $1 \le s_i \le 1000$

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: Y

$X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 혜인이 얻을 수 있는 만족도 합의 최댓값이다.