12463번 - 遊園地 (Small) 다국어채점 준비 중

みんな大好きジェットコースター! この遊園地に来た人はみんなこれがお目当てさ。 1 人で来る人もいるし、グループで来る人もいる。グループで来たからにはやっぱりみんなで一緒じゃないと乗りたくないよね。 楽しい楽しいジェットコースター! このジェットコースター、乗った人はみんなもう一度乗りたがるんだ。 乗車料は一回一人当たり 1 ユーロ。 このジェットコースターの今日の売上を予測するのが君のお仕事さ!

このジェットコースターは同時に k 人乗ることができて、グループが列を作って待っています。 グループは順番にジェットコースターに乗り込み、全部のグループが乗ったか、次に待っているグループ全員が乗れるだけの席が無くなった時点で、空席が残っていたとしても出発します。 ジェットコースターを降りた後、グループは乗り込んだ順番と同じ順番で列の後ろに並びします。 ジェットコースターは 1 日に R 回発車します。

例えば R=4, k=6 の場合に、1 人, 4 人, 2 人, 1 人の 4 つのグループがこの順番に並んでいたとしましょう。 1 回目の出発は 1 人, 4 人の 2 つのグループが乗り込んで、残りひとつの席は空けたまま出発します（次の 2 人のグループは座りきれず、 最後の 1 人のグループは前のグループを抜かすことはできません）。 1 回目が終わった後、彼らは列の後ろに並びなおし、列は 2 人, 1 人, 1 人, 4 人となります。 2 回目は 2 人, 1 人, 1 人の計 4 人が乗り、終わった後の列は 4 人, 2 人, 1 人, 1 人となります。 3 回目は 4 人, 2 人 の計 6 人が乗り、終わった後の列は 1 人, 1 人, 4 人, 2 人となり、最後に 1 人, 1 人, 4 人の計 6 人が乗るので、合計 21 ユーロの売上になります。

1 行目にはテストケースの数 T が含まれており、次の行から T 個のテストケースが後に続きます。 各テストケースは 2 行からなり、始めの行にはスペースで区切られた 3 つの整数 R, k, Nが含まれています。 次の行には N 個のスペースで区切られた整数 g_i が含まれています。 g_i は列に並んでいる各グループの人数を表しており、 g₀ は 1 番目のグループの人数、g₁ は 2 番目のグループの人数、... となっています。

制約

• 1 ≤ T ≤ 50
• g_i ≤ k
• 1 ≤ R ≤ 1000
• 1 ≤ k ≤ 100
• 1 ≤ N ≤ 10
• 1 ≤ g_i ≤ 10

各テストケースにつき 1 行、 "Case #X: Y" と出力してください。ただし、X は 1 から始まるテストケースの番号、Y はジェットコースターのその日の売上です。