Best coffee (Small)

Hyein starts his day by drinking coffee in the morning.

He has $N$ kinds of coffee. Kind $i$ has $c_i$ cups left, and it expires on day $t_i$ counting from today. Every cup of kind $i$ ($1 \le i \le N$) that he drinks gives him satisfaction $s_i$. He cannot drink coffee after its expiry date, but he can still drink it on day $t_i$ itself. For example, if $t_i = 1$, he either drinks that coffee today or gives it up.

Hyein drinks only one cup a day, and only in the morning. On a day when no drinkable coffee is left, he gains no satisfaction.

Find the maximum total satisfaction he can gain from today through day $K$.

The first line contains the number of test cases $T$. Then $T$ test cases follow.

The first line of each test case contains the number of coffee kinds $N$ and the number of days $K$, separated by one space. The next $N$ lines give the remaining cups, the expiry day, and the satisfaction of each kind in this format.

ci ti si

Constraints

• $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$

For each test case, print one line in the following format.

Case #X: Y

$X$ is the test case number starting from 1, and $Y$ is the maximum total satisfaction Hyein can gain.