#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long #define ii pair #define app push_back #define all(a) a.begin(), a.end() #define bp __builtin_popcountll #define ll long long #define mp make_pair #define x first #define y second #define Time (double)clock()/CLOCKS_PER_SEC #define debug(x) std::cerr << #x << ": " << x << '\n'; #define FOR(i, n) for (int i = 0; i < n; ++i) #define FORN(i, n) for (int i = 1; i <= n; ++i) #define pb push_back #define trav(a, x) for (auto& a : x) using vi = vector; template std::istream& operator >>(std::istream& input, std::vector& data) { for (T& x : data) input >> x; return input; } template std::ostream& operator <<(std::ostream& output, const pair & data) { output << "(" << data.x << "," << data.y << ")"; return output; } template std::ostream& operator <<(std::ostream& output, const std::vector& data) { for (const T& x : data) output << x << " "; return output; } ll div_up(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up ll div_down(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down ll math_mod(ll a, ll b) { return a - b * div_down(a, b); } #define tcT template using V = vector; tcT> void re(V& x) { trav(a, x) cin >> a; } tcT> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } // set a = min(a,b) tcT> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } ll gcd(ll a, ll b) { while (b) { tie(a, b) = mp(b, a % b); } return a; } signed main() { #ifdef LOCAL #else #define endl '\n' ios_base::sync_with_stdio(0); cin.tie(0); #endif int t; cin >> t; while (t--) { int n, m, k; cin >> n >> m >> k; V a(n + 1); FOR (i, m) { int x, y; cin >> x >> y; a[x].app(y); } auto Cost = [&] (int c, int x) { int ans = 0; trav (e, a[c]) { ans += (e - x) * (e - x); } return ans; }; auto Get = [&] (int der) { int ans = 0; FORN (c, n) { int l = 0, r = k + 1; while (l < r - 1) { int m = (l + r) / 2; if (Cost(c, m) - Cost(c, m - 1) <= der) { l = m; } else { r = m; } } ans += l; } return ans; }; int der = 2e18; FORN (c, n) { ckmin(der, Cost(c, 1) - Cost(c, 0)); } for (int bit = 40; bit >= 0; --bit) { int nu = der + (1ll << bit); if (Get(nu) <= k) { der = nu; } } auto Get_Cost = [&] (int der) { int ans = 0; FORN (c, n) { int l = 0, r = k + 1; while (l < r - 1) { int m = (l + r) / 2; if (Cost(c, m) - Cost(c, m - 1) <= der) { l = m; } else { r = m; } } ans += Cost(c, l); } return ans; }; assert(der < 1e18); cout << Get_Cost(der) + (k - Get(der)) * (der + 1) << endl; } }