/////////////////////////////////////////////////////////////////////////////
// Writte in
// Claire v3.3.37
// http://www.claire-language.com/
/////////////////////////////////////////////////////////////////////////////
D :: 1000000000
long <: ephemeral_object(hi:integer, lo:integer)
[long!(x: integer) : long ->
long(hi = x / D, lo = x mod D)
]
[+(x:long, y:long) : long ->
let lolo := x.lo - D + y.lo in
(
if ( lolo < 0 )
long(hi = x.hi + y.hi, lo = lolo + D)
else
long(hi = x.hi + y.hi + 1, lo = lolo)
)
]
[-(x:long, y:long) : long ->
let lolo := x.lo - y.lo in
(
if ( lolo < 0 )
long(hi = x.hi - y.hi - 1, lo = lolo + D)
else
long(hi = x.hi - y.hi, lo = lolo)
)
]
[*(x:long, y:integer) : long ->
let r := long!(0) in
let c := x in
(while (y > 0) (
(if (y mod 2 = 1) r :+ c),
c := c + c,
y :/ 2
),
r)
]
[+(x:long, y:integer) : long ->
x + long!(y)
]
[<(x:long, y:long) : boolean ->
if (x.hi < y.hi)
true
else if (x.hi > y.hi)
false
else
x.lo < y.lo
]
[>=(x:long, y:long) : boolean -> not(x < y)]
[<=(x:long, y:long) : boolean -> not(y < x)]
[>(x:long, y:long) : boolean -> (y < x)]
[>=(x:long, y:integer) : boolean -> not(x < long!(y))]
[<=(x:long, y:integer) : boolean -> not(long!(y) < x)]
[<(x:long, y:integer) : boolean -> (x < long!(y))]
[>(x:long, y:integer) : boolean -> (long!(y) < x)]
[>=(x:integer, y:long) : boolean -> not(long!(x) < y)]
[<=(x:integer, y:long) : boolean -> not(y < long!(x))]
[<(x:integer, y:long) : boolean -> (long!(x) < y)]
[>(x:integer, y:long) : boolean -> (y < long!(x))]
[string!(x: long) : string ->
if (x.hi > 0)
let los := string!(x.lo) in
string!(x.hi) /+ make_string(9 - length(los), '0') /+ los
else
string!(x.lo)
]
/////////////////////////////////////////////////////////////////////////////
[readLine() : list<integer> ->
list<integer>{integer!(s) | s in explode(freadline(stdin), " ")}
]
[solve(R:integer, k:integer, N:integer, g:list<integer>) ->
let dest := make_list(N, 0) in
let earn := make_list(N, long!(0)) in
(
for s in (0 .. N - 1) (
let ride := long!(0) in
let i := 0 in
(
while (i < N)
(
let ride2 := ride + g[((s + i) mod N) + 1] in
(if (ride2 > k)
break()
else
(ride := ride2, i :+ 1))
),
earn[s + 1] := ride,
dest[s + 1] := ((s + i) mod N) + 1
)
),
let firstVisitTime := make_list(N, -1) in
let firstVisitEarn := make_list(N, long!(0)) in
let q := 1 in
let totalEarn := long!(0) in
let i := 0 in
(
(while (i < R) (
if (firstVisitTime[q] = -1)
(
firstVisitTime[q] := i,
firstVisitEarn[q] := totalEarn,
totalEarn :+ earn[q],
q := dest[q],
i :+ 1
)
else
(
let loopSize := i - firstVisitTime[q] in
let loopEarn := totalEarn - firstVisitEarn[q] in
let rest := R - i in
(
totalEarn :+ loopEarn * (rest / loopSize),
// clear
firstVisitTime := make_list(N, -1),
i := R - (rest mod loopSize)
)
)
)),
princ(string!(totalEarn))
)
)
]
[main() ->
let T := readLine()[1] in
for C in (1 .. T)
(
printf("Case #~A: ", C),
let RkN := readLine() in solve(RkN[1], RkN[2], RkN[3], readLine()),
princ("\n")
)
]
(main())