use std::cmp::max;
use std::collections::BTreeMap;
use std::iter::{FromIterator,Iterator};
use std::io::{self,Read};
use std::str::Chars;


struct Source<'a> { chars: Chars<'a> }

#[allow(dead_code)]
impl<'a> Source<'a> {
    fn next_chr(&mut self) -> char {
        self.chars.by_ref()
            .skip_while(|c| char::is_whitespace(*c))
            .next()
            .expect("eof")
    }

    fn next_str(&mut self) -> String {
        let it = self.chars.by_ref()
            .skip_while(|c| char::is_whitespace(*c))
            .take_while(|c| !char::is_whitespace(*c));
        let s = String::from_iter(it);
        if s.len() == 0 {
            panic!("eof")
        } else {
            s
        }
    }
}

#[allow(unused_macros)]
macro_rules! input {
    (src = $str:expr; $($elem:tt)*) => {
        let mut src = Source {
            chars: $str.chars(),
        };

        input_inner!(src, $($elem)*)
    };
    ($($elem:tt)*) => {
        let mut data = String::new();
        let stdin= io::stdin();
        stdin.lock().read_to_string(&mut data).expect("Input error");
        let mut src = Source {
            chars: data.chars(),
        };

        input_inner!(src, $($elem)*)
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($src:expr) => {};
    ($src:expr,) => {};
    ($src:expr, $var:ident : mut $ty:tt $($rest:tt)*) => {
        let mut $var = parse!($src, $ty);
        input_inner!($src $($rest)*)
    };
    ($src:expr, $var:ident : $ty:tt $($rest:tt)*) => {
        let $var = parse!($src, $ty);
        input_inner!($src $($rest)*)
    };
}

#[allow(unused_macros)]
macro_rules! parse {
    ($src:expr, ( $($ty:tt),* )) => {
        ( $(parse!($src,$ty)),* )
    };
    ($src:expr, char) => {
        $src.next_chr()
    };
    ($src:expr, [ $ty:tt; $len:expr ]) => {
        (0..$len).map(|_| parse!($src,$ty)).collect::<Vec<_>>()
    };
    ($src:expr, $ty:tt) => {
        parse_str!($src,$ty)
    };
}

#[allow(unused_macros)]
macro_rules! parse_str {
    ($src:expr, chars) => {
        $src.next_str().chars().collect::<Vec<char>>()
    };
    ($src:expr, $ty:ty) => {
        $src.next_str().parse::<$ty>().expect("Parse error")
    };
}

fn remove(k: i64, m: &mut BTreeMap<i64,usize>) {
    let v = match m.get(&k) {
        Some(v) => *v,
        None => 0,
    };
    if v <= 1 {
        m.remove(&k);
    } else {
        m.insert(k,v-1);
    }
}

fn main() {
    input! {
        n: usize, k: usize, td: mut [(usize,i64); n]
    }

    td.sort_by_key(|v| -v.1);

    let mut us = vec![false; n+1];
    let mut res = 0;
    let mut total_d = 0;
    let mut c = 0;
    let mut y = 0;
    let mut i = 0;
    let mut sub = BTreeMap::new();
    for x in 1..k+1 {
        while i < td.len() && (c < k || y < x) {
            let (t,d) = td[i];

            if !us[t] && c == k { // -> y < x
                let d = match sub.iter().next() {
                    Some((d,_)) => *d,
                    None => 0,
                };
                total_d -= d;
                remove(d, &mut sub);
                c -= 1;
            }

            if c < k {
                if !us[t] {
                    y += 1;
                } else {
                    *sub.entry(d).or_insert(0) += 1;
                }
                us[t] = true;
                total_d += d;
                c += 1;
            }

            i += 1;
        }
        if c == k && y >= x {
            res = max(res, y*y+total_d as usize);
        }
    }

    println!("{}", res);
}


Measured memory_bytes: 8444