#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("no-stack-protector")
// #define ll __int128
#define ll long long
// #define ll int
#define f(i,a,b) for(int i=a;i<b;i++)
#define mod 1000000007
// #define mod 998244353 
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(int i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf printf
#define sz(a) (int)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (ll)1e18
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
ll binpow(ll a, ll b, ll md){ll res=1;a%=md;if(a==0)return 0;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
 
using namespace std;

struct node
{
    ll val,lazy,index;
    node()
    {
        val=inf,lazy=0,index=0;
    }
};

vector<node> t;

node merge(node a, node b)
{
    node ans;
    if(a.val<=b.val)
        ans.val=a.val,ans.index=a.index;
    else
        ans.val=b.val,ans.index=b.index;
    return ans;
}

void build(int id, int l, int r)
{
    if(l==r)
    {
        t[id].val=inf,t[id].index=l,t[id].lazy=0;
        return;
    }
    int mid=(l+r)/2;
    build(id<<1,l,mid),build(id<<1|1,mid+1,r);
    t[id]=merge(t[id<<1],t[id<<1|1]);
}

void push(int id, int l, int r)
{
    if(t[id].lazy==0)
        return;
    if(l==r)
    {
        t[id].val+=t[id].lazy,t[id].lazy=0;
        if(t[id].val>inf)
            t[id].val=inf;
        return;
    }
    t[id<<1].lazy+=t[id].lazy,t[id<<1|1].lazy+=t[id].lazy;
    t[id].val+=t[id].lazy,t[id].lazy=0;
}

void update(int id, int l, int r, int lq, int rq, ll p)
{
    push(id,l,r);
    if(l>rq || r<lq)
        return;
    if(l>=lq && r<=rq)
    {
        t[id].lazy+=p;
        push(id,l,r);
        return;
    }
    int mid=(l+r)/2;
    update(id<<1,l,mid,lq,rq,p),update(id<<1|1,mid+1,r,lq,rq,p);
    t[id]=merge(t[id<<1],t[id<<1|1]);
}

node query(int id, int l, int r, int lq, int rq)
{
    push(id,l,r);
    node def_val;
    if(l>rq || r<lq)
        return def_val;
    if(l>=lq && r<=rq)
        return t[id];
    int mid=(l+r)/2;
    return merge(query(id<<1,l,mid,lq,rq),query(id<<1|1,mid+1,r,lq,rq));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("xortransform.in","r",stdin);
    // freopen("xortransform.out","w",stdout);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
// #endif
    int z=1;
    cin>>z;
    f(i,1,z+1)
    {
        //cout<<"Case #"<<i<<": ";
        ll n,k;
        cin>>n>>k;
        vector<array<ll,2> > a(n+1);
        a[0][0]=-inf,a[0][1]=-inf;
        f(i,1,n+1)
        {
            f(j,0,2)
                cin>>a[i][j];
        }
        sort(all(a));
        if(n==2)
        {
            cout<<abs(a[1][0]-a[2][0])+a[1][1]+a[2][1]<<"\n";
            continue;
        }
        else
        {
            ll cnt=k/2-1;
            t.rz(4*n+20);
            build(1,1,n);

            ll tot=0,st=n-cnt,cx=a[st][0];
            vector<ll> suf(n+1,-inf),pre(n+1,-inf);
            f(i,st+1,n+1)
            {
                ll dis=(a[i][1]+2*abs(cx-a[i][0]));
                tot+=dis,update(1,1,n,i,i,-inf+dis);
            }
            suf[st]=tot;

            rf(i,st-1,0)
            {
                ll dif=abs(a[i+1][0]-a[i][0]);
                update(1,1,n,i+1,n,2*dif);
                tot+=(2*dif*cnt);
                node cur=query(1,1,n,1,n);
                
                ll mn=cur.val,id=cur.index,dis=2*dif+a[i+1][1];
                
                if(dis>mn)
                    update(1,1,n,i,i,-inf+dis),tot+=(dis-mn),update(1,1,n,id,id,-mn+inf);

                suf[i]=tot;
            }

            t.clear();
            t.rz(4*n+20);
            build(1,1,n);

            tot=0,st=cnt+1,cx=a[st][0];
            f(i,1,st)
            {
                ll dis=(a[i][1]+2*abs(cx-a[i][0]));
                tot+=dis,update(1,1,n,i,i,-inf+dis);
            }
            pre[st]=tot;

            f(i,st+1,n+1)
            {
                ll dif=abs(a[i-1][0]-a[i][0]);
                update(1,1,n,1,i-1,2*dif);
                tot+=(2*dif*cnt);
                node cur=query(1,1,n,1,n);
                
                ll mn=cur.val,id=cur.index,dis=2*dif+a[i-1][1];
                
                if(dis>mn)
                    update(1,1,n,i,i,-inf+dis),tot+=(dis-mn),update(1,1,n,id,id,-mn+inf);

                pre[i]=tot;
            }

            st=cnt+1;
            ll en=n-cnt,ans=0,ind=en;
            tot=suf[en]+a[en][1];
            rf(i,en-1,st)
            {
                ll dif=abs(a[i][0]-a[i+1][0]),cur=(suf[i+1]+a[i+1][1]+2*dif*cnt);
                tot+=(2*dif*cnt);
                if(a[i+1][0]-a[i][0]+cur>tot+a[ind][0]-a[i][0])
                    tot=cur,ind=i+1;
                ans=max(ans,a[ind][0]-a[i][0]+tot+pre[i]+a[i][1]);
            }

            cout<<ans<<"\n";
        }
    }
}