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() -> (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 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); } (n, k, p) } fn run() { let (n, k, p) = read(); let mut req = vec![vec![]; n]; for &(x, y) in p.iter() { req[x].push(y); } let inf = std::i64::MAX / 2; let mut a = vec![]; for (_, req) in req.iter_mut().enumerate() { req.sort(); let mut pre = 0; for (j, p) in req.iter().enumerate() { a.push((req.len() as i64 - 2 * j as i64, *p - pre)); pre = *p; } a.push((-2 * req.len() as i64, inf)); } a.sort(); let mut rem = k; let mut ans = p.iter().map(|p| p.1).sum::(); for &(d, w) in a.iter().rev() { let v = w.min(rem); rem -= v; ans -= d * v; } println!("{}", ans); } fn main() { run(); }