#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define precision(n) cout << setprecision(n) << fixed
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define pi acos(-1.0)
#define eps 0.0000000001
#define gl(a) scanf("%llu",&a)
#define mod 1000000007
#define pf printf
#define loop(ds,itr) for ( auto itr = ds.begin(); itr != ds.end(); itr++ )
#define fr(i,n) for ( int i = 0; i < n; i++ )
#define check(x) cout << x << endl;
#define bug cout << 'x' << endl;
#define srt(n) (int)(sqrt(double(n))+eps)
#define e 2.71828182845
#define mp make_pair
#define min4(a,b,c,d) min(a,min(b,min(c,d)));
#define power(n,i) (int)(pow(n,i)+eps)
#define inf 0x3f3f3f3f
#define MAX 100005
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#ifdef FACT
#include <ctime>
clock_t tStart = clock();
#define debug(args...) {dbg,args; cerr<<endl;}
#define timeStamp debug ("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
#define bug printf("%d\n",__LINE__);
#else
#define debug(args...)
#define timeStamp
#endif
struct debugger{
template<typename T> debugger & operator , (const T& v){
cerr<<v<<" ";
return *this;
}
}dbg;
typedef long long ll;
typedef unsigned long long ull;
typedef pair < int,int > ii;
typedef priority_queue< int,vector<int>, greater<int> > pq_increasing;
typedef tree< int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
template < class T > inline T gcd(T a, T b){while(b){a%=b;swap(a,b);}return a;}
const int sz = 5015;
int n,k;
ll arr[sz];
ll dp[sz][sz];
ll solve ( int idx , int k ) {
if ( idx == n ) {
return -1e18;
}
if ( dp[idx][k] != -1 ) return dp[idx][k];
ll ans = arr[idx];
if ( arr[idx] >= 0 ) ans = max(ans, solve(idx+1,k) + arr[idx] );
else {
if ( k > 0 ) ans = max(0LL,solve(idx+1,k-1) );
else ans = max(ans,arr[idx]);
}
return dp[idx][k] = ans;
}
int main () {
///freopen("input.txt","r",stdin);
///freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(false);
int t;
sf(t);
for ( int T = 1; T <= t; T++ ) {
memset(dp,-1,sizeof(dp));
sf2(n,k);
fr(i,n) scanf("%lld",&arr[i]);
ll mxm = arr[0];
fr(i,n) {
mxm = max(mxm,solve(i,k));
}
printf("Case %d: %lld\n",T,mxm);
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGUgPGV4dC9wYl9kcy9hc3NvY19jb250YWluZXIuaHBwPgojaW5jbHVkZSA8ZXh0L3BiX2RzL3RyZWVfcG9saWN5LmhwcD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwoKI2RlZmluZSBwcmVjaXNpb24obikgICBjb3V0IDw8IHNldHByZWNpc2lvbihuKSA8PCBmaXhlZAojZGVmaW5lIHNmKGEpICAgICAgICAgIHNjYW5mKCIlZCIsJmEpCiNkZWZpbmUgc2YyKGEsYikgICAgICAgc2NhbmYoIiVkICVkIiwmYSwmYikKI2RlZmluZSBzZjMoYSxiLGMpICAgICBzY2FuZigiJWQlZCVkIiwmYSwmYiwmYykKI2RlZmluZSBwaSAgICAgICAgICAgICBhY29zKC0xLjApCiNkZWZpbmUgZXBzICAgICAgICAgICAgMC4wMDAwMDAwMDAxCiNkZWZpbmUgZ2woYSkgICAgICAgICAgc2NhbmYoIiVsbHUiLCZhKQojZGVmaW5lIG1vZCAgICAgICAgICAgIDEwMDAwMDAwMDcKI2RlZmluZSBwZiAgICAgICAgICAgICBwcmludGYKI2RlZmluZSBsb29wKGRzLGl0cikgICBmb3IgKCBhdXRvIGl0ciA9IGRzLmJlZ2luKCk7IGl0ciAhPSBkcy5lbmQoKTsgaXRyKysgKQojZGVmaW5lIGZyKGksbikgICAgICAgIGZvciAoIGludCBpID0gMDsgaSA8IG47IGkrKyApCiNkZWZpbmUgY2hlY2soeCkgICAgICAgY291dCA8PCB4IDw8IGVuZGw7CiNkZWZpbmUgYnVnICAgICAgICAgICAgY291dCA8PCAneCcgPDwgZW5kbDsKI2RlZmluZSBzcnQobikgICAgICAgICAoaW50KShzcXJ0KGRvdWJsZShuKSkrZXBzKQojZGVmaW5lIGUgICAgICAgICAgICAgIDIuNzE4MjgxODI4NDUKI2RlZmluZSBtcCAgICAgICAgICAgICBtYWtlX3BhaXIKI2RlZmluZSBtaW40KGEsYixjLGQpICBtaW4oYSxtaW4oYixtaW4oYyxkKSkpOwojZGVmaW5lIHBvd2VyKG4saSkgICAgIChpbnQpKHBvdyhuLGkpK2VwcykKI2RlZmluZSBpbmYgICAgICAgICAgICAweDNmM2YzZjNmCiNkZWZpbmUgTUFYICAgICAgICAgICAgMTAwMDA1CiNkZWZpbmUgZmYgICAgICAgICAgICAgZmlyc3QKI2RlZmluZSBzcyAgICAgICAgICAgICBzZWNvbmQKI2RlZmluZSBhbGwodikgICAgICAgICB2LmJlZ2luKCksdi5lbmQoKQoKI2lmZGVmIEZBQ1QKICAgICAjaW5jbHVkZSA8Y3RpbWU+CiAgICAgY2xvY2tfdCB0U3RhcnQgPSBjbG9jaygpOwogICAgICNkZWZpbmUgZGVidWcoYXJncy4uLikge2RiZyxhcmdzOyBjZXJyPDxlbmRsO30KICAgICAjZGVmaW5lIHRpbWVTdGFtcCBkZWJ1ZyAoIkV4ZWN1dGlvbiBUaW1lOiAiLCAoZG91YmxlKShjbG9jaygpIC0gdFN0YXJ0KS9DTE9DS1NfUEVSX1NFQykKICAgICAjZGVmaW5lIGJ1ZyBwcmludGYoIiVkXG4iLF9fTElORV9fKTsKCiNlbHNlCiAgICAjZGVmaW5lIGRlYnVnKGFyZ3MuLi4pCiAgICAjZGVmaW5lIHRpbWVTdGFtcAoKI2VuZGlmCgpzdHJ1Y3QgZGVidWdnZXJ7CiAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBUPiBkZWJ1Z2dlciAmIG9wZXJhdG9yICwgKGNvbnN0IFQmIHYpewogICAgICAgIGNlcnI8PHY8PCIgIjsKICAgICAgICByZXR1cm4gKnRoaXM7CiAgICB9Cn1kYmc7CgoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKdHlwZWRlZiBwYWlyIDwgaW50LGludCA+IGlpOwp0eXBlZGVmIHByaW9yaXR5X3F1ZXVlPCBpbnQsdmVjdG9yPGludD4sIGdyZWF0ZXI8aW50PiA+IHBxX2luY3JlYXNpbmc7CnR5cGVkZWYgdHJlZTwgaW50LCBudWxsX3R5cGUsIGxlc3NfZXF1YWw8aW50PiwgcmJfdHJlZV90YWcsIHRyZWVfb3JkZXJfc3RhdGlzdGljc19ub2RlX3VwZGF0ZSA+IG9yZGVyZWRfc2V0Owp0ZW1wbGF0ZSA8IGNsYXNzIFQgPiBpbmxpbmUgVCBnY2QoVCBhLCBUIGIpe3doaWxlKGIpe2ElPWI7c3dhcChhLGIpO31yZXR1cm4gYTt9Cgpjb25zdCBpbnQgc3ogPSA1MDE1OwppbnQgbixrOwpsbCBhcnJbc3pdOwpsbCBkcFtzel1bc3pdOwoKbGwgc29sdmUgKCBpbnQgaWR4ICwgaW50IGsgKSB7CiAgICBpZiAoIGlkeCA9PSBuICkgewogICAgICAgIHJldHVybiAtMWUxODsKICAgIH0KICAgIGlmICggZHBbaWR4XVtrXSAhPSAtMSApIHJldHVybiBkcFtpZHhdW2tdOwogICAgbGwgYW5zID0gYXJyW2lkeF07CiAgICBpZiAoIGFycltpZHhdID49IDAgKSBhbnMgPSBtYXgoYW5zLCBzb2x2ZShpZHgrMSxrKSArIGFycltpZHhdICk7CiAgICBlbHNlIHsKICAgICAgICBpZiAoIGsgPiAwICkgYW5zID0gbWF4KDBMTCxzb2x2ZShpZHgrMSxrLTEpICk7CiAgICAgICAgZWxzZSBhbnMgPSBtYXgoYW5zLGFycltpZHhdKTsKICAgIH0KICAgIHJldHVybiBkcFtpZHhdW2tdID0gYW5zOwp9CgppbnQgbWFpbiAoKSB7CiAgICAvLy9mcmVvcGVuKCJpbnB1dC50eHQiLCJyIixzdGRpbik7CiAgICAvLy9mcmVvcGVuKCJvdXRwdXQudHh0IiwidyIsc3Rkb3V0KTsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwoKICAgIGludCB0OwogICAgc2YodCk7CiAgICBmb3IgKCBpbnQgVCA9IDE7IFQgPD0gdDsgVCsrICkgewogICAgICAgIG1lbXNldChkcCwtMSxzaXplb2YoZHApKTsKICAgICAgICBzZjIobixrKTsKICAgICAgICBmcihpLG4pIHNjYW5mKCIlbGxkIiwmYXJyW2ldKTsKICAgICAgICBsbCBteG0gPSBhcnJbMF07CiAgICAgICAgZnIoaSxuKSB7CiAgICAgICAgICAgIG14bSA9IG1heChteG0sc29sdmUoaSxrKSk7CiAgICAgICAgfQogICAgICAgIHByaW50ZigiQ2FzZSAlZDogJWxsZFxuIixULG14bSk7CgoKICAgIH0KCgogICAgcmV0dXJuIDA7Cn0K