#include using namespace std; #define rep(i, n) for(long long i=0;i<(long long)(n);i++) #define REP(i,k,n) for(long long i=k;i<(long long)(n);i++) #define pb emplace_back #define lb(v,k) (lower_bound(all(v),(k))-v.begin()) #define ub(v,k) (upper_bound(all(v),(k))-v.begin()) #define fi first #define se second #define pi M_PI #define PQ(T) priority_queue #define SPQ(T) priority_queue,greater> #define dame(a) {out(a);return 0;} #define decimal cout< P; typedef tuple PP; typedef tuple PPP; using vi=vector; using vvi=vector; using vvvi=vector; using vvvvi=vector; using vp=vector

; using vvp=vector; using vb=vector; using vvb=vector; const ll inf=1001001001001001001; const ll INF=1001001001; const ll mod=1000000007; const double eps=1e-10; template bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;} template bool chmax(T&a,T b){if(a void out(T a){cout< void outp(T a){cout<<'('< void outvp(T v){rep(i,v.size())cout<<'('< void outvvp(T v){rep(i,v.size())outvp(v[i]);} template void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout< void outvv(T v){rep(i,v.size())outv(v[i]);} template bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);} template void yesno(T b){if(b)out("yes");else out("no");} template void YesNo(T b){if(b)out("Yes");else out("No");} template void YESNO(T b){if(b)out("YES");else out("NO");} template void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';} void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);} ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);} ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} int main(){ ll tt;cin>>tt; rep(ttt,tt){ ll n,m,k;cin>>n>>m>>k; ll mx=sqrt(1000000000000000000/m)+2; vvi g(n); rep(i,m){ ll a,b;cin>>a>>b;g[a-1].pb(b); } auto cost=[&](ll i,ll u){ ll res=0; for(ll x:g[i])res+=(x-u)*(x-u); return res; }; vi best(n); rep(i,n){ ll l=0,r=mx; while(r-l>3){ ll nl=(l*2+r)/3,nr=(l+r*2)/3; if(cost(i,nl)0){ ll ok=mx,ng=-1; while(ok-ng>1){ ll md=(ok+ng)/2; ll sum=0; rep(i,n){ ll OK=best[i],NG=-1; while(OK-NG>1){ ll MD=(OK+NG)/2; if(cost(i,MD)-cost(i,MD+1)>md)NG=MD; else OK=MD; } sum+=best[i]-OK; } if(sum>=cur)ok=md; else ng=md; } { rep(i,n){ ll OK=best[i],NG=-1; while(OK-NG>1){ ll MD=(OK+NG)/2; if(cost(i,MD)-cost(i,MD+1)>ok)NG=MD; else OK=MD; } best[i]=OK; } } ll a=0,b=0; rep(i,n){ a+=cost(i,best[i]);b+=best[i]; } a-=(k-b)*ok; out(a); } else{ ll ok=mx,ng=-1; while(ok-ng>1){ ll md=(ok+ng)/2; ll sum=0; rep(i,n){ ll OK=best[i],NG=mx+1; while(NG-OK>1){ ll MD=(OK+NG)/2; if(cost(i,MD)-cost(i,MD-1)>md)NG=MD; else OK=MD; } sum+=OK-best[i]; } if(sum>=-cur)ok=md; else ng=md; } // out(ok); { rep(i,n){ ll OK=best[i],NG=mx+1; while(NG-OK>1){ ll MD=(OK+NG)/2; if(cost(i,MD)-cost(i,MD-1)>ok)NG=MD; else OK=MD; } best[i]=OK; } } ll a=0,b=0; rep(i,n){ a+=cost(i,best[i]);b+=best[i]; } a-=(b-k)*ok; out(a); } } }