Morning Coffee (Large)

Kokoa starts every morning with a cup of coffee.

Her cupboard holds $N$ kinds of coffee. Kind $i$ has $c_i$ cups left, and counting today as day 1, it can be drunk up to day $t_i$. Coffee past its date cannot be drunk, but day $t_i$ itself is still fine. If $t_i = 1$, that coffee has to be drunk today or thrown away.

One cup of kind $i$ gives satisfaction $s_i$. Kokoa drinks one cup a day and only in the morning. On a day with no coffee left she gains no satisfaction. Find the largest total satisfaction she can collect from day 1 through day $K$.

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

Each test case starts with a line holding two positive integers separated by one space: the number of coffee kinds $N$ and the number of days $K$ to compute the answer over. The next $N$ lines describe one kind each, giving the cups left, the last drinkable day, and the satisfaction in this format.

ci ti si

The value ranges are as follows.

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le K \le 2 \times 10^{12}$
• $1 \le c_i \le K$
• $1 \le t_i \le K$
• $1 \le s_i \le 1000$

$K$ can exceed the range of a 32 bit integer.

For each test case print one line in this format.

Case #X: Y

$X$ is the test case number starting at 1, and $Y$ is the largest total satisfaction.