SPOJ GSHOP

#include<bits/stdc++.h>
#define pb push_back
#define read freopen("input.txt","r",stdin)
#define write freopen("output.txt","w",stdout)
#define rev(s) std::reverse(s.begin(), s.end())
//#define up std::transform(s.begin(), s.end(), s.begin(), ::toupper);
///string sb=s.substr(1,3);

#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)

#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define max4(a,b,c,d) max(max(a,b),max(c,d))

#define INF (1<<28)
#define mod 1000000007

#define tbeg clock_t _t=clock();
#define tend cout << "\n\nTime: " << (double)(clock()-_t)/CLOCKS_PER_SEC;

#define PI 2*acos(0.0)
#define low std::transform(s.begin(), s.end(), s.begin(), ::tolower);
#define n2s(n) stringstream ss; ss<<n; string Get=ss.str()
#define CC(x) cout<<(x)<<endl
#define srt sort(a,a+n)
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)

typedef long long LL;

using namespace std;

int main()
{
    LL t, n, k, a[105];
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        LL neg = 0, zero = 0, ans = 0;
        memset(a,0,sizeof a);
        rep(i,n)
        {
            cin>>a[i];
            if(a[i]<0){neg++;}
            else if(a[i]==0){zero++;}
        }
        sort(a,a+n);
        if(neg==0){
            if(k%2){a[0] = a[0]*-1;}
            rep(i,n){ans = ans + a[i];}
        }
        else if(neg<=k)
        {
            k = k - neg;
            if(k%2!=0)
            {
                if(zero==0){neg = neg - 1;}
            }
            rep(i,neg){a[i] = a[i]*-1;}
            rep(i,n){ans = ans + a[i];}
        }
        else
        {
            rep(i,k){a[i] = a[i]*-1;}
            rep(i,n){ans = ans + a[i];}
        }
        cout<<ans<<endl;
    }
    return 0;
}