As you know, majority of students and teachers of Summer Informatics School live in Berland for the most part of the year. Since corruption there is quite widespread, the following story is not uncommon.

Elections are coming. You know the number of voters and the number of parties — $n$ and $m$ respectively. For each voter you know the party he is going to vote for. However, he can easily change his vote given a certain amount of money. In particular, if you give $i$-th voter $c_i$ bytecoins you can ask him to vote for any other party you choose.

The United Party of Berland has decided to perform a statistical study — you need to calculate the minimum number of bytecoins the Party needs to spend to ensure its victory. In order for a party to win the elections, it needs to receive strictly more votes than any other party.


-----Input-----

The first line of input contains two integers $n$ and $m$ ($1 \le n, m \le 3000$) — the number of voters and the number of parties respectively.

Each of the following $n$ lines contains two integers $p_i$ and $c_i$ ($1 \le p_i \le m$, $1 \le c_i \le 10^9$) — the index of this voter's preferred party and the number of bytecoins needed for him to reconsider his decision.

The United Party of Berland has the index $1$.


-----Output-----

Print a single number — the minimum number of bytecoins needed for The United Party of Berland to win the elections.


-----Examples-----
Input
1 2
1 100

Output
0

Input
5 5
2 100
3 200
4 300
5 400
5 900

Output
500

Input
5 5
2 100
3 200
4 300
5 800
5 900

Output
600



-----Note-----

In the first sample, The United Party wins the elections even without buying extra votes.

In the second sample, The United Party can buy the votes of the first and the fourth voter. This way The Party gets two votes, while parties $3$, $4$ and $5$ get one vote and party number $2$ gets no votes.

In the third sample, The United Party can buy the votes of the first three voters and win, getting three votes against two votes of the fifth party.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Complete search

Greedy algorithms


Solutions:
(n, m) = map(int, input().split())
cn = []
un = 0
d = {}
for i in range(n):
	(p, c) = map(int, input().split())
	if p == 1:
		un += 1
	else:
		cn.append((p, c))
cn.sort(key=lambda x: x[1])
for i in range(len(cn)):
	(p, c) = cn[i]
	if p not in d:
		d[p] = [(c, i)]
	else:
		d[p].append((c, i))
min_val = 99999999999999999999999
for i in range(1, n // 2 + 2):
	total = 0
	v = set()
	for x in d:
		if len(d[x]) >= i:
			r = len(d[x]) - (i - 1)
			for j in range(0, r):
				total += d[x][j][0]
				v.add(d[x][j][1])
	for j in range(n):
		if len(v) + un >= i:
			break
		if j not in v:
			total += cn[j][1]
			v.add(j)
	min_val = min(total, min_val)
print(min_val)


import collections
import time
import os
import sys
import bisect
import heapq

def solve(N, M, A):
	votes = [[] for _ in range(M + 1)]
	for (p, v) in A:
		votes[p].append(v)
	for p in range(1, M + 1):
		votes[p].sort()
	own = len(votes[1])
	votes = votes[2:]
	votes.sort(reverse=True, key=len)
	size = [len(v) for v in votes]
	if not size or own > size[0]:
		return 0
	nvotes = len(votes)
	ans = float('inf')
	for buy in range((size[0] - own) // 2 + 1, min(N, (N + 1) // 2 + 1) + 1):
		cost = 0
		target = own + buy
		done = 0
		for p in range(nvotes):
			if size[p] >= target:
				t = size[p] - target + 1
				cost += sum(votes[p][:t] or [0])
				done += t
			else:
				break
		if done >= buy:
			ans = min(ans, cost)
		else:
			more = buy - done
			q = []
			for p in range(nvotes):
				t = max(size[p] - target + 1, 0)
				q.extend(votes[p][t:t + more])
			q.sort()
			cost += sum(q[:more])
			ans = min(ans, cost)
	return ans
(N, M) = map(int, input().split())
A = []
for i in range(N):
	(p, v) = map(int, input().split())
	A.append((p, v))
print(solve(N, M, A))


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())
(n, m) = mints()
A = [0] * n
h = [0] * m
for i in range(n):
	(a, b) = mints()
	A[i] = (b, a - 1)
	h[a - 1] += 1
A.sort()
r = 1e+100
for k in range(1, n + 1):
	b = h[:]
	w = [True] * n
	c = 0
	for i in range(n):
		(p, id) = A[i]
		if id != 0 and b[id] >= k:
			b[0] += 1
			b[id] -= 1
			c += p
			w[i] = False
	for i in range(n):
		(p, id) = A[i]
		if id != 0 and w[i] and (b[0] < k):
			b[0] += 1
			b[id] -= 1
			c += p
			w[i] = False
	r = min(r, c)
print(r)


(n, m) = map(int, input().split())
money = [0] * n
for i in range(n):
	(x, y) = map(int, input().split())
	money[i] = (y, x - 1)
money.sort()

def calc(lim):
	visited = [False] * n
	cost = 0
	cnt = [0] * m
	for i in range(n):
		cnt[money[i][1]] += 1
	for i in range(n):
		if money[i][1] != 0 and cnt[money[i][1]] >= lim:
			cnt[money[i][1]] -= 1
			cnt[0] += 1
			cost += money[i][0]
			visited[i] = True
	for i in range(n):
		if cnt[0] >= lim:
			break
		if money[i][1] != 0 and (not visited[i]):
			cnt[money[i][1]] -= 1
			cnt[0] += 1
			cost += money[i][0]
	return cost
ans = 10 ** 18
for i in range(n):
	ans = min(ans, calc(i))
print(ans)


from sys import stdin
(n, m) = map(int, stdin.readline().split())
pc = dict()
ph = dict()
prices = []
for i in range(n):
	(p, c) = map(int, stdin.readline().split())
	if p != 1:
		prices.append(c)
		pc.setdefault(p, []).append(len(prices) - 1)
	ph[p] = ph.setdefault(p, 0) + 1
max_h = 0
for (p, pa) in pc.items():
	pa.sort(reverse=True, key=lambda x: prices[x])
	max_h = max(max_h, len(pa))
hp = [[] for _ in range(max_h + 2)]
for (p, h) in ph.items():
	if p != 1:
		hp[h].append(p)
ans = [0] * (max_h + 2)
sprices_ind = sorted(range(len(prices)), key=lambda x: prices[x])
p_set = set()
height_p1 = ph[1] if 1 in ph else 0
top_sum = 0
top_count = 0
for i in range(max_h + 1, -1, -1):
	if len(prices) < i:
		ans[i] = float('inf')
		continue
	for p in hp[i]:
		p_set.add(p)
	for p in p_set:
		if len(pc[p]) > 0:
			top_ind = pc[p].pop()
			c = prices[top_ind]
			prices[top_ind] = -1
			top_sum += c
			top_count += 1
	ans[i] += top_sum
	if height_p1 + top_count < i:
		k = 0
		for j in range(i - height_p1 - top_count):
			while prices[sprices_ind[k]] == -1:
				k += 1
			ans[i] += prices[sprices_ind[k]]
			k += 1
print(min(ans))


def solve(max_v, votes, m):
	ans = 0
	values = []
	our_v = len(votes[0])
	for i in range(1, m):
		L = len(votes[i])
		if L > max_v:
			take = L - max_v
			our_v += take
			ans += sum(votes[i][:take])
			if take < L:
				values.extend(votes[i][take:])
		else:
			values.extend(votes[i])
	values.sort()
	if our_v <= max_v:
		needed = max_v + 1 - our_v
		if needed <= len(values):
			for i in range(needed):
				ans += values[i]
				our_v += 1
	if our_v <= max_v:
		return 1 << 60
	return ans
(n, m) = [int(x) for x in input().split()]
votes = [[] for x in range(m)]
for i in range(n):
	(p, c) = (int(x) for x in input().split())
	p -= 1
	votes[p].append(c)
for i in range(m):
	L = len(votes[i])
	if L > 1:
		votes[i].sort()
lo = 0
hi = n // 2 + 5
while lo < hi:
	mi = lo + (hi - lo) // 2
	if solve(mi, votes, m) > solve(mi + 1, votes, m):
		lo = mi + 1
	else:
		hi = mi
ans = 1 << 60
E = 20
for i in range(max(0, lo - E), min(lo + E, n + 1)):
	ans = min(ans, solve(i, votes, m))
print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
party = [[] for _ in range(m + 5)]
pc = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[1])
choose = [0] * n
for i in range(n):
	party[pc[i][0]].append(i)
want = 10 ** 18
for i in range(1, n + 1):
	p1 = len(party[1])
	for j in range(2, m + 5):
		if len(party[j]) < i:
			continue
		for k in range(len(party[j]) - i + 1):
			p1 += 1
			choose[party[j][k]] = 1
	want2 = 0
	for j in range(n):
		if p1 < i and choose[j] == 0 and (pc[j][0] != 1):
			choose[j] = 1
			p1 += 1
		if choose[j] == 1:
			want2 += pc[j][1]
	if want > want2:
		want = want2
	choose = [0] * n
print(want)


(n, m) = map(int, input().split())
pc = [(0, 0) for _ in range(n)]
party_votes = [0 for _ in range(m)]
for i in range(n):
	(p, c) = map(int, input().split())
	pc[i] = (p - 1, c)
	party_votes[p - 1] += 1
pc.sort(key=lambda x: x[1])
min_cost = 10 ** 20
for votes in range(n + 1):
	_party_votes = party_votes[:]
	dangerous = list(map(lambda party: _party_votes[party] >= votes, range(0, m)))
	used = list(map(lambda i: pc[i][0] == 0, range(n)))
	cur_cost = 0
	for i in range(n):
		if dangerous[pc[i][0]] and pc[i][0] != 0:
			cur_cost += pc[i][1]
			_party_votes[0] += 1
			_party_votes[pc[i][0]] -= 1
			dangerous[pc[i][0]] = _party_votes[pc[i][0]] >= votes
			used[i] = True
	for i in range(n):
		if _party_votes[0] >= votes:
			break
		if not used[i]:
			_party_votes[0] += 1
			cur_cost += pc[i][1]
	min_cost = min(min_cost, cur_cost)
print(min_cost)


import sys
from collections import defaultdict
(n, m) = map(int, sys.stdin.readline().rstrip('\n').split(' '))
p = defaultdict(list)
for _ in range(n):
	(x, y) = map(int, sys.stdin.readline().rstrip('\n').split(' '))
	p[x].append(y)
for key in p:
	p[key] = sorted(p[key])
ans = 10 ** 100
for k in range(1, n + 1):
	cur = 0
	r = []
	for key in p:
		if key == 1:
			continue
		a = p[key]
		cnt = max(0, len(a) - (k - 1))
		cur += sum(a[:cnt])
		r += a[cnt:]
	r = sorted(r)
	cnt = max(0, len(r) - (n - k))
	cur += sum(r[:cnt])
	ans = min(ans, cur)
print(ans)


import sys
(n, m) = map(int, input().split())
V = [None] * n
for i in range(n):
	V[i] = tuple(map(int, input().split()))
V.sort(key=lambda x: x[1])
if n == 1:
	if V[0][0] == 1:
		print(0)
	else:
		print(V[0][1])
	sys.exit()
Voterlist = [[] for i in range(m + 1)]
Partylist = [0 for i in range(m + 1)]
Vnot1 = []
for i in range(n):
	Voterlist[V[i][0]] += [V[i][1]]
	Partylist[V[i][0]] += 1
	if V[i][0] != 1:
		Vnot1.append(V[i])
Vnot1.sort(key=lambda x: x[1])
maxvote = max(Partylist)
Votenumberlist = [[] for i in range(maxvote + 1)]
for i in range(1, m + 1):
	Votenumberlist[Partylist[i]].append(i)
if Votenumberlist[maxvote] == [1]:
	print(0)
	sys.exit()
ANS = 0
for i in range(maxvote + 1 - Partylist[1]):
	ANS += Vnot1[i][1]
maxvoteminus = 1
while True:
	checkparty = [0 for i in range(m + 1)]
	money = 0
	for i in range(maxvoteminus):
		for j in Votenumberlist[maxvote - i]:
			checkparty[j] += maxvoteminus - i
	for i in range(2, m + 1):
		money += sum(Voterlist[i][:checkparty[i]])
	if money > ANS:
		break
	neednumber = maxvote + 1 - maxvoteminus - Partylist[1]
	for i in range(maxvoteminus):
		neednumber -= len(Votenumberlist[maxvote - i]) * (maxvoteminus - i)
	for pm in Vnot1:
		if checkparty[pm[0]] != 0:
			checkparty[pm[0]] -= 1
		else:
			money += pm[1]
			neednumber -= 1
		if neednumber == 0:
			break
	if money < ANS:
		ANS = money
	maxvoteminus += 1
print(ANS)


import sys
import os

def solve(m, candidates):
	n = len(candidates)
	candidates.sort(key=lambda x: x[1])
	party = dict()
	granted = 0
	for i in range(len(candidates)):
		p = candidates[i][0]
		c = candidates[i][1]
		if p == 1:
			granted += 1
			continue
		if p in party:
			party[p].append((i, c))
		else:
			party[p] = [(i, c)]
	result = None
	for t in range(1, n // 2 + 2):
		total = 0
		chosen = set()
		for (k, v) in party.items():
			if len(v) >= t:
				for i in range(len(v) + 1 - t):
					chosen.add(v[i][0])
					total += v[i][1]
		for i in range(n):
			if len(chosen) + granted >= t:
				break
			if i not in chosen and candidates[i][0] != 1:
				chosen.add(i)
				total += candidates[i][1]
		if result is None:
			result = total
		else:
			result = min(result, total)
	return result

def main():
	(n, m) = map(int, input().split())
	candidates = []
	for i in range(n):
		(p, c) = map(int, input().split())
		candidates.append((p, c))
	print(solve(m, candidates))
main()


class Solver:

	def solve(self):
		(self.num_voters, self.num_parties) = (int(x) for x in input().split())
		self.votes_per_party = [[] for _ in range(self.num_parties)]
		for _ in range(self.num_voters):
			(party, price) = (int(x) for x in input().split())
			party -= 1
			self.votes_per_party[party].append(price)
		for party in range(self.num_parties):
			self.votes_per_party[party].sort()
		max_necessary_votes = self.num_voters // 2 + 1
		cost = lambda min_votes: self.conversion_price_with_fixed_votes(min_votes)
		return self.ternary_search(cost, 0, max_necessary_votes + 2)

	def ternary_search(self, func, begin, end):
		while begin + 1 < end:
			mid = (begin + end - 1) // 2
			if func(mid) <= func(mid + 1):
				end = mid + 1
			else:
				begin = mid + 1
		return func(begin)

	def conversion_price_with_fixed_votes(self, num_votes):
		current_votes = len(self.votes_per_party[0])
		total_cost = 0
		for votes in self.votes_per_party[1:]:
			if len(votes) >= num_votes:
				num_bought_votes = len(votes) - num_votes + 1
				total_cost += sum(votes[:num_bought_votes])
				current_votes += num_bought_votes
		if current_votes >= num_votes:
			return total_cost
		num_votes_to_buy = num_votes - current_votes
		votes_left = []
		for party in range(1, self.num_parties):
			votes_left += self.votes_per_party[party][-(num_votes - 1):]
		votes_left.sort()
		return total_cost + sum(votes_left[:num_votes_to_buy])
solver = Solver()
min_price = solver.solve()
print(min_price)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
men = []
for i in range(n):
	(x, y) = map(int, input().split())
	men.append((y, x - 1))

def solve(lim):
	cnt = [0] * m
	vis = [0] * n
	cost = 0
	for i in range(n):
		cnt[men[i][1]] += 1
	for i in range(n):
		if men[i][1] != 0 and cnt[men[i][1]] >= lim:
			cnt[men[i][1]] -= 1
			cnt[0] += 1
			cost += men[i][0]
			vis[i] = 1
	for i in range(n):
		if cnt[0] < lim and vis[i] == False and (men[i][1] != 0):
			cnt[0] += 1
			cost += men[i][0]
	return cost
men.sort()
ans = 10 ** 18
for i in range(n):
	ans = min(ans, solve(i))
print(ans)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 30, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
				self.temp.count += 1
			if not val:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left
				self.temp.count += 1
		self.temp.data = pre_xor

	def query(self, xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = xor & 1 << i
			if not val:
				if self.temp.left and self.temp.left.count > 0:
					self.temp = self.temp.left
				elif self.temp.right:
					self.temp = self.temp.right
			elif self.temp.right and self.temp.right.count > 0:
				self.temp = self.temp.right
			elif self.temp.left:
				self.temp = self.temp.left
			self.temp.count -= 1
		return xor ^ self.temp.data
(n, m) = map(int, input().split())
d = defaultdict(int)
d1 = defaultdict(list)
l = []
for i in range(n):
	(p, c) = map(int, input().split())
	d[p] += 1
	d1[p].append(c)
	if p != 1:
		l.append(c)
l.sort()
for i in range(1, m + 1):
	d1[i].sort()
tot = 9999999999999999
for i in range(1, n + 1):
	count1 = defaultdict(int)
	for j in l:
		count1[j] += 1
	ans = 0
	cou = 0
	for j in range(2, m + 1):
		if d[j] - i + 1 > 0:
			for k in range(d[j] - i + 1):
				ans += d1[j][k]
				count1[d1[j][k]] -= 1
			cou += d[j] - i + 1
	if d[1] + cou >= i:
		tot = min(ans, tot)
	else:
		for j in range(len(l)):
			if count1[l[j]] > 0:
				ans += l[j]
				cou += 1
				count1[l[j]] -= 1
			if d[1] + cou >= i:
				break
		tot = min(ans, tot)
print(tot)


(n, m) = list(map(int, input().split()))
men = []
for i in range(n):
	(x, y) = list(map(int, input().split()))
	men.append((y, x - 1))

def Calc(lim):
	cnt = [0] * m
	vis = [False] * n
	for i in range(n):
		cnt[men[i][1]] += 1
	cost = 0
	for i in range(n):
		if men[i][1] != 0 and cnt[men[i][1]] >= lim:
			cnt[men[i][1]] -= 1
			cost += men[i][0]
			vis[i] = True
			cnt[0] += 1
	for i in range(n):
		if cnt[0] < lim and vis[i] == False and (men[i][1] != 0):
			cnt[0] += 1
			cost += men[i][0]
	return cost
men.sort()
ans = 10 ** 18
for i in range(n):
	ans = min(ans, Calc(i))
print(ans)


(n, m) = map(int, input().split())
parties = [0 for _ in range(m)]
pairs = []
for i in range(n):
	(p, c) = map(int, input().split())
	parties[p - 1] += 1
	pairs.append((c, p - 1))
pairs.sort()
min_sum = 10 ** 31
for i in range(n, parties[0] - 1, -1):
	cur_sum = 0
	cur_amount = parties[0]
	colours = [0 for _ in range(n)]
	need_to_buy = [max(parties[j] + 1 - i, 0) for j in range(m)]
	need_to_buy[0] = 0
	tmp = sum(need_to_buy)
	if tmp + parties[0] > i:
		print(min_sum)
		exit()
	for j in range(n):
		if need_to_buy[pairs[j][1]] > 0:
			need_to_buy[pairs[j][1]] -= 1
			colours[j] = 1
			cur_amount += 1
			cur_sum += pairs[j][0]
	j = 0
	while cur_amount < i:
		if colours[j] == 0 and pairs[j][1] != 0:
			cur_amount += 1
			cur_sum += pairs[j][0]
		j += 1
	min_sum = min(min_sum, cur_sum)
print(min_sum)


from sys import stdin
from collections import deque
(n, m) = map(int, stdin.readline().split())
pc = dict()
ph = dict()
costs = []

class Cost:

	def __init__(self, id, cost, party) -> None:
		self.id = id
		self.cost = cost
		self.party = party
		self.removed = False
for i in range(n):
	(p, c) = map(int, stdin.readline().split())
	if p != 1:
		cost = Cost(i, c, p)
		costs.append(cost)
		pc.setdefault(p, []).append(cost)
	ph[p] = ph.setdefault(p, 0) + 1
max_h = 0
for (p, pa) in pc.items():
	pa.sort(reverse=True, key=lambda x: x.cost)
	max_h = max(max_h, len(pa))
hp = [[] for _ in range(max_h + 2)]
for (p, h) in ph.items():
	if p != 1:
		hp[h].append(p)
ans = [0] * (max_h + 2)
costs.sort(key=lambda x: x.cost)
dq = deque(costs)
p_set = set()
height_p1 = ph[1] if 1 in ph else 0
top_sum = 0
top_count = 0
for i in range(max_h + 1, -1, -1):
	if len(costs) < i:
		ans[i] = float('inf')
		continue
	for p in hp[i]:
		p_set.add(p)
	for p in p_set:
		if len(pc[p]) > 0:
			min_cost = pc[p].pop()
			min_cost.removed = True
			top_sum += min_cost.cost
			top_count += 1
	ans[i] += top_sum
	if height_p1 + top_count < i:
		for j in range(i - height_p1 - top_count):
			while dq[0].removed:
				dq.popleft()
			ans[i] += dq[0].cost
			dq.rotate(-1)
		dq.rotate(i - height_p1 - top_count)
print(min(ans))


(n, m) = map(int, input().split())
parties = [[] for i in range(m)]
for i in range(n):
	(x, y) = map(int, input().split())
	parties[x - 1].append(y)
for i in range(m):
	parties[i].sort(reverse=True)
mi = len(parties[0])
cost = float('inf')
for i in range(mi, n + 1):
	temp = 0
	to_chose = []
	collected = mi
	for j in range(1, m):
		count = 0
		for k in parties[j]:
			count += 1
			if count >= i:
				temp += k
				collected += 1
			else:
				to_chose.append(k)
	to_chose = sorted(to_chose)
	if collected >= i:
		cost = min(cost, temp)
	if len(to_chose) < i - collected:
		continue
	for j in range(0, i - collected):
		temp += to_chose[j]
	cost = min(cost, temp)
print(cost)


import sys

def pro():
	return sys.stdin.readline().strip()

def rop():
	return map(int, pro().split())
(a, s) = rop()
q = [0] * a
w = [0] * s
for i in range(a):
	(n, p) = rop()
	q[i] = (p, n - 1)
	w[n - 1] += 1
q.sort()
t = 1e+100
for k in range(1, a + 1):
	p = w[:]
	r = [True] * a
	m = 0
	for i in range(a):
		(po, rty) = q[i]
		if rty != 0 and p[rty] >= k:
			p[0] += 1
			p[rty] -= 1
			m += po
			r[i] = False
	for i in range(a):
		(po, rty) = q[i]
		if rty != 0 and r[i] and (p[0] < k):
			p[0] += 1
			p[rty] -= 1
			m += po
			r[i] = False
	t = min(t, m)
print(t)


def solve(N, M, A):
	pv = [0] * M
	pm = [[] for _ in range(M)]
	allm = {}
	for (p, c) in A:
		p -= 1
		pv[p] += 1
		if p == 0:
			continue
		pm[p].append(c)
		if c not in allm:
			allm[c] = 0
		allm[c] += 1
	for m in pm:
		m.sort()
	allml = list(allm)
	allml.sort()
	maxv = max(pv)
	best = 10 ** 9 * 3000 + 1
	for iv in range(1, min(maxv + 2, N + 1)):
		allmrest = dict(allm)
		cost = 0
		reqd = 0
		if pv[0] < iv:
			reqd = iv - pv[0]
		got = 0
		for i in range(1, M):
			if pv[i] >= iv:
				ad = pv[i] - iv + 1
				for j in range(ad):
					cost += pm[i][j]
					allmrest[pm[i][j]] -= 1
				got += ad
		if reqd > got:
			for m in allml:
				c = allmrest[m]
				toget = min(reqd - got, c)
				cost += toget * m
				got += toget
				if reqd == got:
					break
		if reqd > got:
			continue
		best = min(best, cost)
	return best

def main():
	(N, M) = [int(e) for e in input().split(' ')]
	A = [[int(e) for e in input().split(' ')] for _ in range(N)]
	print(solve(N, M, A))
main()