12455번 - 最高のコーヒー (Small) 다국어

ヘインの一日は朝のコーヒーを飲むことから始まります。

彼の手元には N 種類のコーヒーがあります。i 番目の種類のコーヒーは c_i 杯分残っていて、今日から数えて t_i 日目に消費期限を迎えます。彼は i 番目（1 ≤ i ≤ N）の種類のコーヒーを一杯飲むごとに s_iの満足度が得られます。消費期限の切れたコーヒーを飲むことはできません（ちょうど t_i 日目であればそのコーヒーは飲むことができます）。たとえば t_i = 1 であれば、今日中に飲んでしまうか、そのコーヒーをあきらめるかのどちらかにしなければなりません。

彼はコーヒーを一日に一杯だけ、朝だけにしか飲まないことにしています。もし手元に飲めるコーヒーがない日は、満足度を得ることはできません。

これらのコーヒーを飲むことで、今日から始めて K 日目までに彼は合計して最大でどれだけの満足度を得られるでしょうか。

入力の最初の行はテストケースの個数 T です。そのあとに T 個のテストケースが続きます。 それぞれのテストケースは 1 つのスペースで区切られた 2 つの正の整数が含まれる行から始まります。 最初の整数はコーヒーの種類数 N を表し、次の整数は日数 K を表します。 そのあとにそれぞれの種類のコーヒーの残数、消費期限、満足度を表す以下の形式の行が N 行続きます。

ci ti si

制約

• 1 ≤ T ≤ 100
• 1 ≤ c_i ≤ K
• 1 ≤ t_i ≤ K
• 1 ≤ s_i ≤ 1000
• 1 ≤ N ≤ 8
• 1 ≤ K ≤ 8

各テストケースごとに、

Case #X: Y

と一行出力してください。ここで X は 1 から始まるテストケースの番号、Y はヘインの満足度の合計の最大値です。