There is a long-established secondhand bookstore called JOI secondhand bookstore in your town, and you often use the JOI secondhand bookstore. Each book has a standard price, and you can buy it at that price if you go to the JOI secondhand bookstore.

At the JOI secondhand bookstore, books are classified into 10 genres such as novels, manga, and magazines. Genres are numbered from 1 to 10. The JOI secondhand bookstore has a service that if you buy books of the same genre in bulk, they will buy them at a high price. Specifically, when books of the same genre are purchased together in T books, the purchase price per book of that genre is T -1 yen higher than the standard price. For example, if books of the same genre with standard prices of 100 yen, 120 yen, and 150 yen are sold together at the JOI secondhand bookstore, the purchase prices will be 102 yen, 122 yen, and 152 yen, respectively.

By the way, you have to move in a hurry due to personal reasons. You have N books, but it is difficult to bring all the books to your new home, so I decided to sell K of the N books to the JOI secondhand bookstore.



input

Read the following input from standard input.

* The integers N and K are written on the first line, separated by blanks, indicating that the number of books you have is N, of which K books will be sold to JOI secondhand bookstores.
* The following N lines contain information about your book. On the first line of i + (1 ≤ i ≤ N), the integers Ci and Gi are written separated by blanks, indicating that the base price of the i-th book is Ci and the genre number is Gi. ..

output

Output an integer representing the maximum value of the total purchase price to the standard output on one line.

Example

Input

7 4
14 1
13 2
12 3
14 2
8 2
16 3
11 2


Output

60

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def solve():
	(n, k) = map(int, input().split())
	group_num = 10
	book_map = [[] for i in range(group_num)]
	acc_map = [[0] for i in range(group_num)]
	for i in range(n):
		(c, g) = map(int, input().split())
		book_map[g - 1].append(c)
	for i in range(group_num):
		bmi = book_map[i]
		bmi.sort(reverse=True)
		ami = acc_map[i]
		acc = 0
		for j in range(len(bmi)):
			acc += bmi[j] + j * 2
			ami.append(acc)
	dp = [[0] * (k + 1) for i in range(group_num + 1)]
	for y in range(1, k + 1):
		for x in range(1, group_num + 1):
			accs = acc_map[x - 1]
			dp_pre = dp[x - 1]
			dp[x][y] = max([dp_pre[y - z] + accs[z] for z in range(min(y + 1, len(accs)))])
	print(dp[group_num][k])
solve()


import sys

def solve():
	file_input = sys.stdin
	(N, K) = map(int, file_input.readline().split())
	G = [[] for i in range(10)]
	for line in file_input:
		(c, g) = map(int, line.split())
		G[g - 1].append(c)
	for genre in G:
		genre.sort(reverse=True)
		for (i, p) in zip(range(1, len(genre)), genre):
			genre[i] += p + 2 * i
	C = [0] * (K + 1)
	for genre in G:
		pre_C = C.copy()
		for (n, p) in zip(range(len(genre), 0, -1), genre[::-1]):
			for (i, vals) in enumerate(zip(pre_C[n:], C)):
				(v1, v2) = vals
				v1 += p
				if v1 > v2:
					C[i] = v1
	print(C[0])
solve()


def solve():
	(n, k) = map(int, input().split())
	group_num = 10
	book_map = [[] for i in range(group_num)]
	acc_map = [[0] for i in range(group_num)]
	for i in range(n):
		(c, g) = map(int, input().split())
		book_map[g - 1].append(c)
	for i in range(group_num):
		bmi = book_map[i]
		bmi.sort(reverse=True)
		append = acc_map[i].append
		acc = 0
		for j in range(len(bmi)):
			acc += bmi[j] + j * 2
			append(acc)
	dp = [[0] * (k + 1) for i in range(group_num + 1)]
	for y in range(1, k + 1):
		for x in range(1, group_num + 1):
			mp = acc_map[x - 1]
			be = dp[x - 1]
			dp[x][y] = max([be[y - z] + mp[z] for z in range(min(y + 1, len(mp)))])
	print(dp[group_num][k])
solve()


from itertools import accumulate
(n, k) = map(int, input().split())
books = [[] for _ in range(10)]
while n:
	(c, g) = map(int, input().split())
	books[g - 1].append(c)
	n -= 1
books_acc = [[0] + list(accumulate((c + i * 2 for (i, c) in enumerate(sorted(q, reverse=True))))) for q in books]

def memoize(f):
	memo = [[-1] * (k + 1) for _ in range(10)]

	def main(x, y):
		if x > 9:
			return 0
		result = memo[x][y]
		if result < 0:
			result = memo[x][y] = f(x, y)
		return result
	return main

@memoize
def combi(g, remain):
	book_acc = list(books_acc[g])
	salable = min(remain + 1, len(book_acc))
	return max([book_acc[i] + combi(g + 1, remain - i) for i in range(salable)], default=0)
print(combi(0, k))


def main():
	import sys
	input = sys.stdin.readline
	(n, k) = map(int, input().split())
	ab = [list(map(int, input().split())) for _ in [0] * n]
	g = [[] for _ in [0] * 10]
	[g[b - 1].append(a) for (a, b) in ab]
	[g[c].sort(reverse=True) for c in range(10)]
	for c in range(10):
		g[c] = [0] + g[c]
	for c in range(10):
		for i in range(2, len(g[c])):
			g[c][i] += g[c][i - 1] + 2 * (i - 1)
	dp = [0] * (k + 1)
	for c in range(10):
		dp2 = [0] * (k + 1)
		for i in range(len(g[c])):
			for j in range(k + 1 - i):
				dp2[i + j] = max(dp2[i + j], dp[j] + g[c][i])
		dp = dp2
	print(max(dp))
main()


def solve():
	(n, k) = map(int, input().split())
	group_num = 10
	book_map = [[] for i in range(group_num)]
	acc_map = []
	for i in range(n):
		(c, g) = map(int, input().split())
		book_map[g - 1].append(c)
	for i in range(group_num):
		bmi = book_map[i]
		bmi.sort(reverse=True)
		ami = [0 for i in range(len(bmi) + 1)]
		for j in range(len(bmi)):
			ami[j + 1] = ami[j] + bmi[j] + j * 2
		acc_map.append(ami)
	dp = [[0] * (k + 1) for i in range(group_num + 1)]
	for y in range(1, k + 1):
		for x in range(1, group_num + 1):
			accs = acc_map[x - 1]
			dp_pre = dp[x - 1]
			dp[x][y] = max([dp_pre[y - z] + accs[z] for z in range(min(y + 1, len(accs)))])
	print(dp[group_num][k])
solve()


def solve():
	(N, K) = map(int, input().split())
	a = [[] for _ in [0] * 10]
	l = []
	for (c, g) in (tuple(map(int, input().split())) for _ in [0] * N):
		a[g - 1].append(c)
	for (i, prices) in enumerate(a):
		ln = len(prices)
		if ln == 0:
			continue
		dp = [0] * (K + 1)
		for (j, price) in enumerate(prices):
			_k = j if j < K - 1 else K - 1
			for (k, prev, cur) in zip(range(_k, -1, -1), dp[_k::-1], dp[_k + 1::-1]):
				if prev + price + k * 2 > cur:
					dp[k + 1] = prev + price + k * 2
		l.append(dp[1:ln + 1])
	dp = [float('-inf')] * (K + 1)
	dp[0] = 0
	for prices in l:
		cdp = dp[:]
		for (i, price) in enumerate(prices, start=1):
			if i > K:
				break
			for (j, cur, prev) in zip(range(K, -1, -1), cdp[::-1], dp[K - i::-1]):
				if 0 < prev + price > cur:
					cdp[j] = prev + price
		dp = cdp
	print(max(dp))
solve()


from heapq import heappush as push
from heapq import heappop as pop

def solve():
	(n, k) = map(int, input().split())
	group_num = 10
	book_map = [[] for i in range(group_num)]
	acc_map = [[0] for i in range(group_num)]
	for i in range(n):
		(c, g) = map(int, input().split())
		push(book_map[g - 1], -c)
	for i in range(group_num):
		bmi = book_map[i]
		append = acc_map[i].append
		acc = 0
		for j in range(len(bmi)):
			acc += pop(bmi) - j * 2
			append(acc)
	dp = [[0] * (k + 1) for i in range(group_num + 1)]
	for y in range(1, k + 1):
		for x in range(1, group_num + 1):
			mp = acc_map[x - 1]
			be = dp[x - 1]
			for z in range(min(y + 1, len(mp))):
				v1 = be[y - z]
				v2 = mp[z]
				if dp[x][y] > v1 + v2:
					dp[x][y] = v1 + v2
	print(-dp[group_num][k])
solve()


def solve():
	(n, k) = map(int, input().split())
	group_num = 10
	book_map = [[] for i in range(group_num)]
	acc_map = [[0] for i in range(group_num)]
	for i in range(n):
		(c, g) = map(int, input().split())
		book_map[g - 1].append(c)
	for i in range(group_num):
		book_map[i].sort(reverse=True)
		acc = 0
		for j in range(len(book_map[i])):
			book_map[i][j] += j * 2
			acc += book_map[i][j]
			acc_map[i].append(acc)
	dp = [[0] * (k + 1) for i in range(group_num + 1)]
	for y in range(1, k + 1):
		for x in range(1, group_num + 1):
			for z in range(min(y + 1, len(acc_map[x - 1]))):
				dp[x][y] = max(dp[x][y], dp[x - 1][y - z] + acc_map[x - 1][z])
	print(dp[group_num][k])
solve()


def solve():
	(n, k) = map(int, input().split())
	group_num = 10
	book_map = [[] for i in range(group_num)]
	acc_map = [[0] for i in range(group_num)]
	for i in range(n):
		(c, g) = map(int, input().split())
		book_map[g - 1].append(c)
	for i in range(group_num):
		book_map[i].sort(reverse=True)
		acc = 0
		bmi = book_map[i]
		append = acc_map[i].append
		for j in range(len(bmi)):
			acc += bmi[j] + j * 2
			append(acc)
	dp = [[0] * (k + 1) for i in range(group_num + 1)]
	for y in range(1, k + 1):
		for x in range(1, group_num + 1):
			mp = acc_map[x - 1]
			be = dp[x - 1]
			for z in range(min(y + 1, len(mp))):
				v1 = be[y - z]
				v2 = mp[z]
				if dp[x][y] < v1 + v2:
					dp[x][y] = v1 + v2
	print(dp[group_num][k])
solve()


import sys

def solve():
	file_input = sys.stdin
	(N, K) = map(int, file_input.readline().split())
	G = [[] for i in range(10)]
	for line in file_input:
		(c, g) = map(int, line.split())
		G[g - 1].append(c)
	for genre in G:
		genre.sort(reverse=True)
		for (p, i) in zip(genre, range(1, len(genre))):
			genre[i] += p + 2 * i
	C = [0] * (K + 1)
	for genre in G:
		pre_C = C.copy()
		for (n, p) in enumerate(genre, start=1):
			for (i, vals) in enumerate(zip(pre_C[n:], C)):
				(v1, v2) = vals
				v1 += p
				if v1 > v2:
					C[i] = v1
	print(C[0])
solve()