'use strict'

class Main {
  solve() {
    const nums = input.nextIntArr();
    const k = nums[1];
    const table = input.nextIntRange(nums[0]);
    const score = [];

    table.sort((a,b) => -(a[1] - b[1]));
    const s = _.first(table, k);
    const kinds = {};
    s.forEach(e => kinds[e[0]] = (kinds[e[0]] ? kinds[e[0]] + 1: 1));
    let kind = Object.keys(kinds).length;
    score[kind] = _.sum(s.map(s => s[1]));

    const heap = [];
    s.forEach(e => {
      if (kinds[e[0]] > 1) {
        heap.push(e);
      }
    });
    heap.sort((a,b) => a[1] - b[1]);
    let cur = k;
    while (heap.length > 0 && cur < table.length) {
      const target = heap.pop();
      if (kinds[target[0]] >= 2) {
        --kinds[target[0]];
        do {
          let next = table[cur];
          ++cur;
          if (kinds[next[0]] === undefined) {
            kinds[next[0]] = 1;
            ++kind;
            score[kind] = score[kind - 1] + next[1] - target[1];
            break;
          }
        } while(cur < table.length);
      }
    }

    const scores = score.map((e,i) => e ? (e + i * i) : 0);
    console.log(_.max(scores));
  }
}

class Input {
  constructor() {
    this.cursor = 0;
    this.inputAll();
  }

  inputAll() {
    this.data = (require("fs").readFileSync("/dev/stdin", "utf8")).split('\n');
    return this.data;
  }

  nextLine(n) {
    if (n) {
      const ret = this.data.slice(this.cursor, this.cursor + n);
      this.cursor += n;
      return ret;
    }
    return this.data[this.cursor++];
  }

  nextStrArr() {
    return this.nextLine().split(' ');
  }

  nextIntArr() {
    return this.nextStrArr().map((e) => parseInt(e));
  }

  nextStrRange(n) {
    return this.nextLine(n).map((line) => line.split(' '));
  }

  nextIntRange(n) {
    return this.nextLine(n).map((line) => line.split(' ').map((e) => parseInt(e)));
  }
}

/* Underscore.js の移植および便利メソッド群 */
class Underscore {
  sum(arr) { return arr.reduce((a,b)=>a+b); }
  min(arr, func) { if (func == null) {func = (a,b) => a - b} return arr.reduce((a,b) => func(a,b) < 0 ? a : b); }
  max(arr, func) { if (func == null) {func = (a,b) => a - b} return arr.reduce((a,b) => func(a,b) > 0 ? a : b); }

  range(start, stop, step) {
	if (stop == null) {
	  stop = start || 0;
	  start = 0;
	}
	if (!step) {
	  step = stop < start ? -1 : 1;
	}
	const length = Math.max(Math.ceil((stop - start) / step), 0);
	const range = Array(length);

	for (var idx = 0; idx < length; idx++, start += step) {
	  range[idx] = start;
	}
	return range;
  }

  first (array, n) {
    if (array == null || array.length < 1) return n == null ? void 0 : [];
    if (n == null) return array[0];
    return this.initial(array, array.length - n);
  };

  initial (array, n) { return array.slice.call(array, 0, Math.max(0, array.length - (n == null ? 1 : n))); }

  tail(arr, n) { return array.slice.call(arr, n == null ? 1 : n); }

  last (array, n) { 
    if (n == null) return array[array.length - 1];
    return this.tail(array, Math.max(0, array.length - n)); 
  }

  binarySearch (array, key, iteratee) {
	const itr = (obj) => (typeof obj === 'object') ? obj[iteratee] : obj;
	const value = itr(obj);
	let low = 0, high = array.length;
	while (low < high) {
	  let mid = Math.floor((low + high) / 2);
	  if (itr(array[mid]) < value) low = mid + 1; else high = mid;
	}
	return low;
  };
}
const _ = new Underscore();

const input = new Input();
(new Main()).solve();
