Problem: Everyone who has played Cut the Rope knows full well how the gameplay is organized. All levels in the game are divided into boxes. Initially only one box with some levels is available. Player should complete levels to earn stars, collecting stars opens new box with levels.

<image>

Imagine that you are playing Cut the Rope for the first time. Currently you have only the levels of the first box (by the way, it is called "Cardboard Box"). Each level is characterized by two integers: ai — how long it takes to complete the level for one star, bi — how long it takes to complete the level for two stars (ai < bi).

You want to open the next box as quickly as possible. So, you need to earn at least w stars. How do make it happen? Note that the level can be passed only once: either for one star or for two. You do not necessarily need to pass all the levels.

Input

The first line contains two integers n and w (1 ≤ n ≤ 3·105; 1 ≤ w ≤ 2n) — the number of levels in the first box and the number of stars you need to open another box. Each of the following n lines contains two integers ai and bi (1 ≤ ai < bi ≤ 109) — the attributes of the i-th level.

Output

In the first line print integer t — the minimum time you need to open the next box. 

In the next line, print n digits without spaces — the description of the optimal scenario: 

  * if you need to pass the i-th level for one star, the i-th digit should equal 1; 
  * if you need to pass the i-th level for two stars, the i-th digit should equal 2; 
  * if you do not need to pass the i-th level at all, the i-th digit should equal 0. 

Examples

Input

2 3
1 2
1 2


Output

3
12


Input

5 3
10 20
5 10
10 20
6 9
25 30


Output

14
01020

Note

In the first test sample, answer 21 is also assumed correct.

Solution (in JAVA):

Solution:
import java.util.HashMap;
import java.util.Comparator;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.util.Map;
import java.util.List;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.TreeMap;
import java.util.ArrayList;
import java.util.Set;
import java.util.TreeSet;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int w = in.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        Utils.readIntArrays(in, a, b);
        Node[] nodes = new Node[n];
        Node root;
        for (int i = 0; i < n; ++i) {
            nodes[i] = new Node();
            nodes[i].a = a[i];
            nodes[i].b = b[i];
            nodes[i].id = i;
            nodes[i].key = a[i];
            nodes[i].sum = a[i];
            nodes[i].addToSum = 0;
        }

        Arrays.sort(nodes, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.b != o2.b) return o1.b - o2.b;
                return o1.id - o2.id;
            }
        });

        root = nodes[0];
        for (int i = 1; i < n; ++i) {
            root = CartesianTree.insertByKey(root, nodes[i]);
        }
        dfsUpdate(root);
        long result = getCurrentResult(root, w);
        int bestPrefix = 0;
        long sum = 0;
        for (int i = 0; i < n; ++i) {
            root = CartesianTree.removeByKey(root, nodes[i].key);
            Node newNode = new Node();
            sum += nodes[i].a;
            newNode.key = nodes[i].b - nodes[i].a;
            newNode.sum = newNode.key;
            root = CartesianTree.insertByKey(root, newNode);
            int prefixLength = i + 1;
            if (w < prefixLength) break;
            long cur = getCurrentResult(root, w - prefixLength);
            if (cur < Long.MAX_VALUE) {
                cur += sum;
            }
            if (result > cur) {
                result = cur;
                bestPrefix = prefixLength;
            }
        }
        out.println(result);

        for (int i = 0; i < n; ++i) {
            nodes[i] = new Node();
            nodes[i].a = a[i];
            nodes[i].b = b[i];
            nodes[i].id = i;
            nodes[i].key = a[i];
            nodes[i].sum = a[i];
            nodes[i].addToSum = 0;
            nodes[i].left = null;
            nodes[i].right = null;
        }

        Arrays.sort(nodes, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.b != o2.b) return o1.b - o2.b;
                return o1.id - o2.id;
            }
        });
        root = nodes[0];
        for (int i = 1; i < n; ++i) {
            root = CartesianTree.insertByKey(root, nodes[i]);
        }
        dfsUpdate(root);
        for (int i = 0; i < bestPrefix; ++i) {
            root = CartesianTree.removeByKey(root, nodes[i].key);
            Node newNode = new Node();
            newNode.key = nodes[i].b - nodes[i].a;
            newNode.sum = newNode.key;
            root = CartesianTree.insertByKey(root, newNode);
        }

        TreeMap<Integer, Set<Integer>> aToIdsTaken = new TreeMap<Integer, Set<Integer>>();
        TreeMap<Integer, Set<Integer>> aToIdsNotTaken = new TreeMap<Integer, Set<Integer>>();
        Map<Integer, Integer> bMinusA = new HashMap<Integer, Integer>();

        int[] taken = new int[n];
        for (int i = 0; i < bestPrefix; ++i) {
            putToMap(nodes[i].a, nodes[i].id, aToIdsTaken);
        }
        for (int i = bestPrefix; i < n; ++i) {
            putToMap(nodes[i].a, nodes[i].id, aToIdsNotTaken);
        }
        Node[] p = CartesianTree.splitByPosition(root, w - bestPrefix, new Node[] {null, null});
        dfs(p[0], aToIdsTaken, aToIdsNotTaken, bMinusA);
        for (int idx : aToIdsTaken.keySet()) {
            for (int x : aToIdsTaken.get(idx)) {
                taken[x] = 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (taken[i] == 1) {
                if (bMinusA.containsKey(b[i] - a[i])) {
                    removeFromMap(bMinusA, b[i] - a[i]);
                    taken[i] = 2;
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            out.print(taken[i]);
        }
        out.println();
    }

    private void dfsUpdate(Node v) {
        if (v == null) return;
        dfsUpdate(v.left);
        dfsUpdate(v.right);
        v.updateData();
    }

    private void removeFromMap(Map<Integer, Integer> m, int x) {
        if (m.get(x) == 1) m.remove(x);
        else {
            m.put(x, m.get(x) - 1);
        }
    }

    private void dfs(Node v, Map<Integer, Set<Integer>> aToIdsTaken, Map<Integer, Set<Integer>> aToIdsNotTaken, Map<Integer, Integer> bMinusA) {
        if (v == null) return;
        if (aToIdsNotTaken.containsKey(v.key)) {
            TreeSet<Integer> cur = (TreeSet<Integer>) aToIdsNotTaken.get(v.key);
            int id = cur.first();
            cur.remove(id);
            putToMap(v.key, id, aToIdsTaken);
            if (cur.size() > 0) {
                aToIdsNotTaken.put(v.key, cur);
            } else {
                aToIdsNotTaken.remove(v.key);
            }
        } else {
            putToMap2(v.key, bMinusA);
        }
        dfs(v.left, aToIdsTaken, aToIdsNotTaken, bMinusA);
        dfs(v.right, aToIdsTaken, aToIdsNotTaken, bMinusA);
    }

    private void putToMap2(int key, Map<Integer, Integer> m) {
        if (m.containsKey(key)) {
            m.put(key, m.get(key) + 1);
        } else {
            m.put(key, 1);
        }
    }

    private void putToMap(int key, int id, Map<Integer, Set<Integer>> m) {
        if (m.containsKey(key)) {
            Set<Integer> s = m.get(key);
            s.add(id);
            m.put(key, s);
        } else {
            Set<Integer> s = new TreeSet<Integer>();
            s.add(id);
            m.put(key, s);
        }
    }

    private long getCurrentResult(Node root, int prefixLength) {
        if (root.size < prefixLength) {
            return Long.MAX_VALUE;
        }
        Node[] p = CartesianTree.splitByPosition(root, prefixLength, new Node[] {null, null});
        long sum = 0;
        if (p[0] != null) {
            sum = p[0].sum;
        }
        root = CartesianTree.merge(p[0], p[1]);
        return sum;
    }

    class Node extends CartesianTree.OpenNode<Node> {
        long sum;
        int a, b;
        int id;
        long addToSum;

        protected void pushData() {
            if (addToSum != 0) {
                if (this.left != null) {
                    this.left.sum += addToSum;
                    this.left.addToSum += addToSum;
                }
                if (this.right != null) {
                    this.right.sum += addToSum;
                    this.right.addToSum += addToSum;
                }
                addToSum = 0;
            }
        }

        protected void updateData() {
            assert addToSum == 0;
            this.sum = this.key;
            if (this.left != null) {
                this.sum += this.left.sum;
            }
            if (this.right != null) {
                this.sum += this.right.sum;
            }
        }
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine().trim();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

}

class Utils {

    public static void readIntArrays(InputReader in, int[]... a) {
        for (int i = 0; i < a[0].length; ++i) {
            for (int j = 0; j < a.length; ++j) {
                a[j][i] = in.nextInt();
            }
        }
    }

}

class CartesianTree {
    /**
     * Base class for a node of cartesian tree.
     * @param <Node>
     */
    public static abstract class OpenNode<Node extends OpenNode<Node>> {
        public static Random r = new Random(3731);

        public Node left, right, parent;
        public int priority;
        public int size;
        public int key;

        protected OpenNode() {
            this.size = 1;
            this.priority = r.nextInt();
        }

        public void push() {
            if (this == null) return;
            updateParent();
            pushData();
        }

        public void update() {
            if (this == null) return;
            updateParent();
            updateData();
            updateSize();
        }

        protected void updateSize() {
            size = 1;
            if (left != null) size += left.size;
            if (right != null) size += right.size;
        }

        /**
         * If the node has a lazy tag, pushes the changes to its children.
         */
        protected abstract void pushData();

        /**
         * Recalculates the information in the node after its children have
         * changed.
         */
        protected abstract void updateData();

        protected void updateParent() {
            if (left != null) {
                left.parent = (Node) this;
            }

            if (right != null) {
                right.parent = (Node) this;
            }
        }
    }

    public static  <Node extends OpenNode<Node>> int size(Node x) {
        if (x == null) return 0;
        return x.size;
    }

    public static <Node extends OpenNode<Node>> Node merge(Node left, Node right) {
        if (left == null) return right;
        if (right == null) return left;
        left.push();
        right.push();
        if (left.priority > right.priority) {
            left.right = merge(left.right, right);
            left.update();
            return left;
        } else {
            right.left = merge(left, right.left);
            right.update();
            return right;
        }
    }

    public static <Node extends OpenNode<Node>> Node[] splitByKey(Node x, int key) {
        if (x == null) {
            return (Node[]) new OpenNode[]{null, null};
        }
        x.push();
        Node[] p;
        if (key < x.key) {
            p = splitByKey(x.left, key);
            x.left = p[1];
            p[1] = x;
        } else {
            p = splitByKey(x.right, key);
            x.right = p[0];
            p[0] = x;
        }
        if (p[0] != null) p[0].update();
        if (p[1] != null) p[1].update();
        return p;
    }

    public static <Node extends OpenNode<Node>> Node insertByKey(Node t, Node it) {
        if (t == null) {
            return it;
        }
        t.push();
        if (it.priority > t.priority) {
            Node[] p = splitByKey(t, it.key);
            it.left = p[0];
            it.right = p[1];
            t = it;
        } else {
            if (it.key < t.key) {
                if (t.left == null) {
                    t.left = it;
                } else {
                    t.left = insertByKey(t.left, it);
                }
            } else {
                if (t.right == null) {
                    t.right = it;
                } else {
                    t.right = insertByKey(t.right, it);
                }
            }
        }
        t.update();
        return t;
    }

    public static <Node extends OpenNode<Node>> Node[] splitByPosition(Node x, int left, Node[] empty) {
        if (x == null) {
            return empty.clone();
        }
        x.push();
        Node[] p;
        if (left <= size(x.left)) {
            p = splitByPosition(x.left, left, empty);
            x.left = p[1];
            p[1] = x;
        } else {
            p = splitByPosition(x.right, left - size(x.left) - 1, empty);
            x.right = p[0];
            p[0] = x;
        }
        if (p[0] != null) p[0].update();
        if (p[1] != null) p[1].update();
        return p;
    }


    public static <Node extends OpenNode<Node>> Node removeByKey(Node t, int key) {
        t.push();
        if (t.key == key) {
            t = CartesianTree.merge(t.left, t.right);
        } else {
            if (key < t.key) {
                t.left = removeByKey(t.left, key);
            } else {
                t.right = removeByKey(t.right, key);
            }
        }
        if (t != null) t.update();
        return t;
    }
}