const MAX_T: usize = 100; const MAX_N: usize = 200_000; const MAX_M: usize = 200_000; const MAX_K: i64 = 1_000_000_000; const MAX_Y: i64 = 1_000_000_000; fn read() -> Vec<(usize, i64, Vec<(usize, i64)>)> { let mut s = String::new(); use std::io::Read; std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let mut next = || it.next().unwrap().parse::().unwrap(); let t = next() as usize; assert!(1 <= t && t <= MAX_T); let mut test = vec![]; for _ in 0..t { let n = next() as usize; assert!(1 <= n && n <= MAX_N); let m = next() as usize; assert!(1 <= m && m <= MAX_M); let k = next(); assert!(1 <= k && k <= MAX_K); let mut p = vec![(0usize, 0i64); m]; for p in p.iter_mut() { p.0 = next() as usize; assert!(1 <= p.0 && p.0 <= n); p.0 -= 1; p.1 = next(); assert!(1 <= p.1 && p.1 <= MAX_Y); } assert!( m.saturating_mul(k.max(p.iter().map(|p| p.1).max().unwrap()) as usize) <= 10usize.pow(18) ); test.push((n, k, p)); } test } fn wrong(n: usize, k: i64, p: &[(usize, i64)]) -> i64 { let mut dp = vec![(0, 0, 0); n]; for &(x, y) in p.iter() { let po = &mut dp[x]; po.0 += y * y; po.1 -= 2 * y; po.2 += 1; } let eval = |m: i64| -> (i64, i64) { if m >= 0 { let mut cnt = 0; let mut cost = 0; let mut zero = false; for &(c, b, a) in dp.iter() { cost += c; zero |= a == 0; if a > 0 && 0 >= a + b { let x = (0 - (a + b)) / (2 * a) + 1; cnt += x; cost += 2 * a * (x - 1) * x / 2 + (a + b) * x; } } if zero { cnt += k; } if cnt >= k { return (cnt, cost); } } let mut cnt = 0; let mut cost = 0; let mut p = vec![0; n]; for (p, &(c, b, a)) in p.iter_mut().zip(dp.iter()) { cost += c; if a > 0 && m >= a + b { let x = (m - (a + b)) / (2 * a) + 1; cnt += x; *p = x; cost += 2 * a * (x - 1) * x / 2 + (a + b) * x; } } (cnt, cost) }; let mut ng = dp.iter().map(|&(_, b, a)| 2 * a + a + b - 1).min().unwrap(); let mut ok = dp.iter().map(|&(_, b, a)| 2 * a * k + a + b).min().unwrap(); while ok - ng > 1 { let mid = (ok + ng) / 2; if eval(mid).0 >= k { ok = mid; } else { ng = mid; } } let (x, y) = eval(ok); let ans = y - ok * (x - k); ans } fn main() { let test = read(); for (n, k, p) in test { let ans = wrong(n, k, &p); println!("{}", ans); } }