Є \(N\) пиріжків. Кожен з пиріжків має два параметри: 'вид начинки' \(t_i\) і 'смачність' \(d_i\). Ви обираєте \(K\) пиріжків для їжі. Ваше 'задоволення' буде розраховуватися наступним чином:

• Задоволення - це сума 'базових загальних смаків' та бонус за різноманітність.

• Базовий загальний смак це сума смаків пиріжків, які ви їсте.

• Бонус за різноманітність - \(x*x\), де \(x\) - кількість різних видів начинки пиріжків.

Ви збираєтеся отримати якомога більше задоволення. Знайдіть це максимальне значення.

Формат вхідних даних

Перший рядок вхідного потоку містить два цілі числа \(N,K\) (\(1 \le K \le N \le 10^5\)).

Наступні \(N\) рядків містять пари цілих чисел \(t_i, d_i\) (\(1 \le t_i \le N\), \(1 \le d_i \le 10^9\)).

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести максимальне значення задоволення.

Примітка

До прикладу 1:

Якщо ви їсте пиріжки 1,2 та 3: базова загальна смакота становить 9 + 7 + 6 = 22. Бонус за різноманітність становить 2*2=4. Таким чином, ваше задоволення буде 26, що є оптимальним.

Приклад вхідних даних

5 3
1 9
1 7
2 6
2 5
3 1

Приклад вихідних даних

26

Приклад вхідних даних

7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5

Приклад вихідних даних

25