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 ≤ n, m ≤ 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 ≤ p_i ≤ m, 1 ≤ c_i ≤ 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.
/* Author: Ronak Agarwal, reader part not written by me*/
import java.io.* ; import java.util.* ;
import static java.lang.Math.min ; import static java.lang.Math.max ;
import static java.lang.Math.abs ; import static java.lang.Math.log ;
import static java.lang.Math.pow ; import static java.lang.Math.sqrt ;
/* Thread is created here to increase the stack size of the java code so that recursive dfs can be performed */
public class Codeshefcode{
	public static void main(String[] args) throws IOException{
		new Thread(null,new Runnable(){	public void run(){ exec_Code() ;} },"Solver",1l<<27).start() ;
	}
	static void exec_Code(){
		try{
			Solver Machine = new Solver() ;
			Machine.Solve() ; Machine.Finish() ;}
		catch(Exception e){ e.printStackTrace() ; print_and_exit() ;}
		catch(Error e){ e.printStackTrace() ; print_and_exit() ; }
	}
	static void print_and_exit(){ System.out.flush() ; System.exit(-1) ;}
}
/* Implementation of the Reader class */
class Reader { 
	private InputStream mIs;
	private byte[] buf = new byte[1024];
	private int curChar,numChars;
	public Reader() { this(System.in); } 
	public Reader(InputStream is) { mIs = is;} 
	public int read() {
		if (numChars == -1) throw new InputMismatchException();    
		if (curChar >= numChars) {
			curChar = 0;
			try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}
			if (numChars <= 0) return -1;            
		}
		return buf[curChar++];
	} 
	public String nextLine(){
		int c = read();
		while (isSpaceChar(c)) c = read();        
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString() ;
	} 
	public String s(){
		int c = read();
		while (isSpaceChar(c)) c = read();        
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		}while (!isSpaceChar(c));
		return res.toString();
	} 
	public long l(){
		int c = read();
		while (isSpaceChar(c)) c = read();        
		int sgn = 1;
		if (c == '-') { sgn = -1 ; c = read() ; }
		long res = 0;
		do{
			if (c < '0' || c > '9') throw new InputMismatchException();
			res *= 10 ; res += c - '0' ; c = read();
		}while(!isSpaceChar(c));
		return res * sgn;
	} 
	public int i(){
		int c = read() ;
		while (isSpaceChar(c)) c = read();        
		int sgn = 1;
		if (c == '-') { sgn = -1 ; c = read() ; }
		int res = 0;
		do{
			if (c < '0' || c > '9') throw new InputMismatchException();
			res *= 10 ; res += c - '0' ; c = read() ;
		}while(!isSpaceChar(c));
		return res * sgn;
	} 
	public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } 
	public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; } 
}   
/* All the useful functions,constants,renamings are here*/
class Template{
	/* Constants Section */
	final int INT_MIN = Integer.MIN_VALUE ; final int INT_MAX = Integer.MAX_VALUE ;
	final long LONG_MIN = Long.MIN_VALUE ; final long LONG_MAX = Long.MAX_VALUE ;
	static long MOD = 1000000007 ;
	static Reader ip = new Reader() ;	
	static PrintWriter op = new PrintWriter(System.out) ;
	/* Methods for writing */
	static void p(Object o){ op.print(o) ; }
	static void pln(Object o){ op.println(o) ;}
	static void Finish(){ op.flush(); op.close(); }
	/* Implementation of operations modulo MOD */
	static long inv(long a){ return powM(a,MOD-2) ; }
	static long m(long a,long b){ return (a*b)%MOD ; }
	static long d(long a,long b){ return (a*inv(b))%MOD ; }
	static long powM(long a,long b){
		if(b<0) return powM(inv(a),-b) ;
		long ans=1 ;
		for( ; b!=0 ; a=(a*a)%MOD , b/=2) if((b&1)==1) ans = (ans*a)%MOD ;
		return ans ;
	}
	/* Renaming of some generic utility classes */
	final static class mylist extends ArrayList<pair>{}
	final static class myset extends TreeSet<pair>{}
	final static class mystack extends Stack<Integer>{}
	final static class mymap extends TreeMap<Integer,Integer>{}
	
}
/* Implementation of the pair class, useful for every other problem */
class pair implements Comparable<pair>{
	long x ; int y ;
	pair(long _x,int _y){ x=_x ; y=_y ;} 
	public int compareTo(pair p){
		return (this.x<p.x ? -1 : (this.x>p.x ? 1 : (this.y<p.y ? -1 : (this.y>p.y ? 1 : 0)))) ;
	}
}
/* Main code starts here */
class Solver extends Template{
	int n,m;
	int p[],frq[];
	long c[];
	long paym[][];
	long ppay[][];
	int ptr[];
	long cost(int wvote){
		// pln("Aaya with wvote="+wvote);
		for(int i=1 ; i<=m ; i++) ptr[i]=0;
		long res=0; long votes=frq[1];
		// pln("Votes are "+votes);
		for(int i=2 ; i<=m ; i++){
			if(frq[i]>=wvote){ 
				res+=ppay[i][frq[i]-wvote]; 
				ptr[i] = (frq[i]-wvote+1);
				votes+=(frq[i]-wvote+1);
			}
		}
		// pln("After cutting of votes are "+votes);
		if(votes>=wvote) return res;
		myset set = new myset();
		for(int i=2 ; i<=m ; i++) if(ptr[i]<frq[i]) set.add(new pair(paym[i][ptr[i]],i));
		// p("Set has elements: ");
		// for(pair elem : set){
		// 	p("("+elem.x+","+elem.y+") ");
		// }
		// pln("");
		while(votes!=wvote){
			if(set.isEmpty()) return LONG_MAX;
			res+=set.first().x;
			int i = set.pollFirst().y;
			ptr[i]++;
			if(ptr[i]<frq[i]) set.add(new pair(paym[i][ptr[i]],i));
			votes++;
		}
		// pln("");
		return res;
	}
 	public void Solve() throws IOException{
 		n = ip.i();
 		m = ip.i();
 		p = new int[n+1]; c = new long[n+1];
 		ptr = new int[m+1];
 		for(int i=1 ; i<=n ; i++){ 
 			p[i] = ip.i(); c[i] = ip.i();
 		}
 		if(n==1 && p[1]!=1){
 			pln(c[1]);
 			return;
 		}
 		frq = new int[m+1];
 		paym = new long[m+1][];
 		ppay = new long[m+1][];
 		for(int i=1 ; i<=n ; i++) frq[p[i]]++;
 		boolean flag = true;
 		for(int i=2 ; i<=m ; i++) if(frq[i]>=frq[1]) flag=false;
 		if(flag){
 			pln(0);
 			return;
 		}
 		for(int i=1 ; i<=m ; i++) paym[i] = new long[frq[i]];
 		for(int i=1 ; i<=n ; i++){
 			int j = p[i];
 			paym[j][ptr[j]++] = c[i];
 		}
 		for(int i=1 ; i<=m ; i++) Arrays.sort(paym[i]);
 		for(int i=1 ; i<=m ; i++) ppay[i] = new long[frq[i]];
 		for(int i=1 ; i<=m ; i++){
 			long parr[] = ppay[i];
 			long arr[] = paym[i];
 			int len = frq[i];
 			for(int j=0 ; j<len ; j++) parr[j] = (j!=0 ? parr[j-1] : 0)+arr[j];
 		}
 		long min_cost = LONG_MAX;
 		for(int i=max(2,frq[1]) ; (2*i)<=(n+2); i++){
 			long vote_cost = cost(i);
 			min_cost = min(min_cost,vote_cost);
 		}
 		pln(min_cost);
 	}
} 
