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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.Collections;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * @author khokharnikunj8
 */

public class Main {
        public static void main(String[] args) {
                new Thread(null, new Runnable() {
                        public void run() {
                                new Main().solve();
                        }
                }, "1", 1 << 26).start();
        }

        void solve() {
                InputStream inputStream = System.in;
                OutputStream outputStream = System.out;
                ScanReader in = new ScanReader(inputStream);
                PrintWriter out = new PrintWriter(outputStream);
                CElections solver = new CElections();
                solver.solve(1, in, out);
                out.close();
        }

        static class CElections {
                ArrayList<Integer>[] arrays;

                public void solve(int testNumber, ScanReader in, PrintWriter out) {
                        int n = in.scanInt();
                        int m = in.scanInt();
                        arrays = new ArrayList[m + 1];
                        for (int i = 0; i <= m; i++) arrays[i] = new ArrayList<>();
                        for (int i = 0; i < n; i++) {
                                int pi = in.scanInt();
                                int ci = in.scanInt();
                                arrays[pi].add(ci);
                        }
                        for (int i = 0; i <= m; i++) Collections.sort(arrays[i]);
                        long ans = Long.MAX_VALUE;
                        if (arrays[1].size() >= n / 2 + 1) {
                                out.println(0);
                                return;
                        }
                        out:
                        for (int i = arrays[1].size(); i <= n / 2 + 1; i++) {
                                long cost = 0;
                                int size = i - arrays[1].size();
                                BSTCustom<Integer> tt = new BSTCustom<Integer>(true);
                                for (int j = 2; j <= m; j++) {
                                        for (int k = 0; k < arrays[j].size(); k++) {
                                                if (k <= arrays[j].size() - i) {
                                                        cost += arrays[j].get(k);
                                                        size--;
                                                } else tt.insert(arrays[j].get(k));
                                        }
                                }
                                while (size-- > 0) {
                                        int temp = tt.getLowest();
                                        cost += temp;
                                        tt.remove(temp, 1);
                                }
                                ans = Math.min(ans, cost);
                        }
                        out.println(ans);

                }

        }

        static class ScanReader {
                private byte[] buf = new byte[4 * 1024];
                private int index;
                private BufferedInputStream in;
                private int total;

                public ScanReader(InputStream inputStream) {
                        in = new BufferedInputStream(inputStream);
                }

                private int scan() {
                        if (index >= total) {
                                index = 0;
                                try {
                                        total = in.read(buf);
                                } catch (Exception e) {
                                        e.printStackTrace();
                                }
                                if (total <= 0) return -1;
                        }
                        return buf[index++];
                }

                public int scanInt() {
                        int integer = 0;
                        int n = scan();
                        while (isWhiteSpace(n)) n = scan();
                        int neg = 1;
                        if (n == '-') {
                                neg = -1;
                                n = scan();
                        }
                        while (!isWhiteSpace(n)) {
                                if (n >= '0' && n <= '9') {
                                        integer *= 10;
                                        integer += n - '0';
                                        n = scan();
                                }
                        }
                        return neg * integer;
                }

                private boolean isWhiteSpace(int n) {
                        if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
                        else return false;
                }

        }

        static class BSTCustom<T extends Comparable<? super T>> {
                private Node<T> __root;
                private Node<T> __tempnode;
                private Node<T> __tempnode1;
                private long __size;
                private boolean __multi;

                public BSTCustom() {
                        __root = null;
                        __size = 0;
                        __multi = false;

                }

                public BSTCustom(boolean __multi) {
                        __root = null;
                        __size = 0;
                        this.__multi = __multi;
                }

                private Node<T> remove(Node<T> temp, T data, long count) {
                        if (temp == null) return temp;
                        int _comparator = data.compareTo(temp.data);
                        if (_comparator < 0) temp._left = remove(temp._left, data, count);
                        else if (_comparator > 0) temp._right = remove(temp._right, data, count);
                        else {
                                if (__multi && count < temp.count && temp.count > 1) {
                                        __size -= count;
                                        temp.count -= count;
                                } else {
                                        __size -= temp.count;
                                        if (temp._left == null && temp._right == null) return null;
                                        else if (temp._left == null) return temp._right;
                                        else if (temp._right == null) return temp._left;
                                        else {
                                                __tempnode = minValue(temp._right);
                                                temp.data = __tempnode.data;
                                                temp.count = __tempnode.count;
                                                temp._right = remove(temp._right, __tempnode.data, __tempnode.count);
                                                __size += temp.count;
                                        }
                                }
                        }
                        // for __leftside and _rightside count
                        if (temp._left != null)
                                temp._leftside = temp._left._leftside + temp._left._rightside + temp._left.count;
                        else temp._leftside = 0;
                        if (temp._right != null)
                                temp._rightside = temp._right._leftside + temp._right._rightside + temp._right.count;
                        else temp._rightside = 0;

                        temp._height = Math.max(getheight(temp._left), getheight(temp._right)) + 1;
                        //Balancing

                        long diff = getDiff(temp);
                        if (diff > 1) {
                                if (getDiff(temp._left) >= 0) {
                                        temp = rightRotate(temp);
                                } else {
                                        temp._left = leftRotate(temp._left);
                                        temp = rightRotate(temp);
                                }
                        } else if (diff < -1) {
                                if (getDiff(temp._right) <= 0) {
                                        temp = leftRotate(temp);
                                } else {
                                        temp._right = rightRotate(temp._right);
                                        temp = leftRotate(temp);
                                }
                        }
                        return temp;
                }

                public T getLowest() {
                        __tempnode = __root;
                        if (__tempnode == null) return null;
                        while (__tempnode._left != null) __tempnode = __tempnode._left;
                        return __tempnode.data;
                }

                private Node<T> minValue(Node<T> temp) {
                        __tempnode = temp;
                        while (__tempnode._left != null) __tempnode = __tempnode._left;
                        return __tempnode;
                }

                public void insert(T data, long... count) {
                        if (count.length == 0) __root = insert(__root, data, 1);
                        else if (count[0] > 0) __root = insert(__root, data, count[0]);

                }

                public void remove(T data, long... count) {
                        if (count.length == 0) __root = remove(__root, data, 1);
                        else if (count[0] > 0) __root = remove(__root, data, count[0]);

                }

                private Node<T> insert(Node<T> temp, T data, long count) {
                        if (temp == null) {
                                if (__multi) {
                                        __size += count;
                                        return new Node<>(data, count);
                                } else {
                                        __size++;
                                        return new Node<>(data);
                                }
                        }
                        int _comparator = data.compareTo(temp.data);
                        if (_comparator < 0) temp._left = insert(temp._left, data, count);
                        else if (_comparator > 0) temp._right = insert(temp._right, data, count);
                        else if (__multi) {
                                __size += count;
                                temp.count += count;
                        }


                        // for __leftside and _rightside count
                        if (temp._left != null)
                                temp._leftside = temp._left._leftside + temp._left._rightside + temp._left.count;
                        else temp._leftside = 0;
                        if (temp._right != null)
                                temp._rightside = temp._right._leftside + temp._right._rightside + temp._right.count;
                        else temp._rightside = 0;

                        temp._height = Math.max(getheight(temp._left), getheight(temp._right)) + 1;
                        //Balancing

                        long diff = getDiff(temp);
                        if (diff > 1) {
                                if (data.compareTo(temp._left.data) < 0) {
                                        temp = rightRotate(temp);
                                } else if (data.compareTo(temp._left.data) > 0) {
                                        temp._left = leftRotate(temp._left);
                                        temp = rightRotate(temp);
                                }
                        } else if (diff < -1) {
                                if (data.compareTo(temp._right.data) > 0) {

                                        temp = leftRotate(temp);
                                } else if (data.compareTo(temp._right.data) < 0) {
                                        temp._right = rightRotate(temp._right);
                                        temp = leftRotate(temp);
                                }
                        }
                        return temp;

                }

                private Node<T> rightRotate(Node<T> temp) {
                        __tempnode = temp._left;
                        __tempnode1 = __tempnode._right;

                        __tempnode._right = temp;
                        temp._left = __tempnode1;

                        //height updation
                        temp._height = Math.max(getheight(temp._left), getheight(temp._right)) + 1;
                        __tempnode._height = Math.max(getheight(__tempnode._left), getheight(__tempnode._right)) + 1;
                        //count updation

                        if (temp._left != null)
                                temp._leftside = temp._left._leftside + temp._left._rightside + temp._left.count;
                        else temp._leftside = 0;
                        if (temp._right != null)
                                temp._rightside = temp._right._leftside + temp._right._rightside + temp._right.count;
                        else temp._rightside = 0;

                        if (__tempnode._left != null)
                                __tempnode._leftside = __tempnode._left._leftside + __tempnode._left._rightside + __tempnode._left.count;
                        else __tempnode._leftside = 0;
                        if (__tempnode._right != null)
                                __tempnode._rightside = __tempnode._right._leftside + __tempnode._right._rightside + __tempnode._right.count;
                        else __tempnode._rightside = 0;


                        return __tempnode;
                }

                private Node<T> leftRotate(Node<T> temp) {
                        __tempnode = temp._right;
                        __tempnode1 = __tempnode._left;

                        __tempnode._left = temp;
                        temp._right = __tempnode1;

                        //height updation
                        temp._height = Math.max(getheight(temp._left), getheight(temp._right)) + 1;
                        __tempnode._height = Math.max(getheight(__tempnode._left), getheight(__tempnode._right)) + 1;
                        //count updation

                        if (temp._left != null)
                                temp._leftside = temp._left._leftside + temp._left._rightside + temp._left.count;
                        else temp._leftside = 0;
                        if (temp._right != null)
                                temp._rightside = temp._right._leftside + temp._right._rightside + temp._right.count;
                        else temp._rightside = 0;


                        if (__tempnode._left != null)
                                __tempnode._leftside = __tempnode._left._leftside + __tempnode._left._rightside + __tempnode._left.count;
                        else __tempnode._leftside = 0;
                        if (__tempnode._right != null)
                                __tempnode._rightside = __tempnode._right._leftside + __tempnode._right._rightside + __tempnode._right.count;
                        else __tempnode._rightside = 0;

                        return __tempnode;
                }

                private long getDiff(Node<T> temp) {
                        if (temp == null) return 0;
                        return getheight(temp._left) - getheight(temp._right);
                }

                public long getheight(Node<T> temp) {
                        if (temp == null) return 0;
                        return temp._height;
                }

                private class Node<T> {
                        T data;
                        Node<T> _left;
                        Node<T> _right;
                        long _leftside;
                        long _rightside;
                        long _height;
                        long count;

                        public Node(T data) {
                                this.data = data;
                                this._left = null;
                                this._right = null;
                                this._leftside = 0;
                                this._rightside = 0;
                                this._height = 1;
                                this.count = 1;
                        }

                        public Node(T data, long count) {
                                this.data = data;
                                this._left = null;
                                this._right = null;
                                this._leftside = 0;
                                this._rightside = 0;
                                this._height = 1;
                                this.count = count;
                        }

                }

        }
}

