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.io.*;
import java.util.*;

public class e11 {
	BufferedReader br;
	StringTokenizer in;
	PrintWriter out;
	
	static Node main_root;
	static Random q = new Random(0);
	static int[] answ;

	static class Node {
		Node l, r;
		int y, size, id, type;
		long x, sum;

		Node(long m, int id1, int t1) {
			x = m;
			id = id1;
			y = q.nextInt(100000);
			size = 1;
			sum = m;
			type = t1;
		}
	}

	static class level implements Comparable<level> {
		long a;
		long b;
		int id;

		level(long a1, long b1, int id1) {
			a = a1;
			b = b1;
			id = id1;
		}

		@Override
		public int compareTo(level o) {
			if (this.b < o.b) {
				return -1;
			} else {
				if (this.b == o.b) {
					return 0;
				} else {
					return 1;
				}
			}
		}
	}

	static void resize(Node a) {
		if (a != null) {
			int sum = 1;
			if (a.l != null) {
				sum += a.l.size;
			}
			if (a.r != null) {
				sum += a.r.size;
			}
			a.size = sum;
		}
	}

	static void resum(Node a) {
		if (a != null) {
			long sum = a.x;
			if (a.l != null) {
				sum += a.l.sum;
			}
			if (a.r != null) {
				sum += a.r.sum;
			}
			a.sum = sum;
		}
	}

	static Node merge(Node a, Node b) {
		if (a == null) {
			return b;
		}
		if (b == null) {
			return a;
		}
		if (a.y > b.y) {
			a.r = merge(a.r, b);
			resize(a);
			resum(a);
			return a;
		} else {
			b.l = merge(a, b.l);
			resize(b);
			resum(b);
			return b;
		}
	}

	static Node[] split(Node root, long key, int id1) {
		Node[] nodes = new Node[2];
		if (root != null) {
			if (root.x > key) {
				Node[] nodes1 = split(root.l, key, id1);
				nodes[0] = nodes1[0];
				nodes[1] = root;
				root.l = nodes1[1];
			} else {
				if (root.x == key) {
					if (root.id > id1) {
						Node[] nodes1 = split(root.l, key, id1);
						nodes[0] = nodes1[0];
						nodes[1] = root;
						root.l = nodes1[1];
					} else {
						Node[] nodes1 = split(root.r, key, id1);
						nodes[0] = root;
						root.r = nodes1[0];
						nodes[1] = nodes1[1];
					}
				} else {
					Node[] nodes1 = split(root.r, key, id1);
					nodes[0] = root;
					root.r = nodes1[0];
					nodes[1] = nodes1[1];
				}
			}
			resize(root);
			resum(root);
		} else {
			nodes[0] = null;
			nodes[1] = null;
		}
		return nodes;
	}

	static boolean exist(Node root, long x) {
		if (root == null) {
			return false;
		}
		if (root.x == x) {
			return true;
		} else {
			if (root.x > x) {
				return exist(root.l, x);
			} else {
				return exist(root.r, x);
			}
		}
	}

	static Node insert(Node q) {
		Node[] nodes = split(main_root, q.x, q.id);
		main_root = merge(merge(nodes[0], q), nodes[1]);
		return main_root;
	}

	static Node remove(Node root, long key, int id) {
		Node a;
		Node[] t1 = split(root, key, id);
		Node[] t2 = split(t1[0], key, id - 1);
		a = merge(t2[0], t1[1]);
		return a;
	}

	static long get_sum(long k, Node root) {
		if (k <= 0) {
			return 0;
		} else {
			if (root == null) {
				return 0;
			} else {
				if ((root.l != null) && (root.l.size > k)) {
					return get_sum(k, root.l);
				} else {
					if ((root.l != null) && (root.l.size == k)) {
						return root.l.sum;
					} else {
						if ((root.l != null) && (root.r != null)) {
							return root.l.sum + root.x
									+ get_sum(k - root.l.size - 1, root.r);
						} else {
							if (root.l == null) {
								if (root.r == null) {
									return root.x;
								} else {
									return (get_sum(k - 1, root.r) + root.x);
								}
							} else {
								return root.sum;
							}
						}
					}
				}
			}
		}
	}

	static void get_ans(long k, Node root) {
		if ((root == null) || (k == 0)) {
			return;
		} else {
			if ((root.l != null) && (root.l.size >= k)) {
				get_ans(k, root.l);
			} else {
				get_ans(k, root.l);
				answ[root.id] = root.type;
				if (root.l == null) {
					get_ans(k - 1, root.r);
				} else {
					get_ans(k - root.l.size - 1, root.r);
				}
			}
		}
	}


	
	public String nextToken() throws IOException {
		while (in == null || !in.hasMoreTokens()) {
			in = new StringTokenizer(br.readLine());
		}
		return in.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public static void main(String[] args) throws IOException {
		new e11().run();
	}

	public void solve() throws IOException {
		int n = nextInt();
		int w = nextInt();
		level[] levels = new level[n];
		for (int i = 0; i < n; i++) {
			int a = nextInt();
			int b = nextInt();
			levels[i] = new level(a, b, i);
			main_root = insert(new Node(a, levels[i].id, 1));
		}
		Arrays.sort(levels);
		long ans = Long.MAX_VALUE;
		long sum = 0;
		int cnt = 0;
		for (int i = 0; i < Math.min(w, n); i++) {
			if (main_root.size >= w - i) {
				ans = Math.min(get_sum(w - i, main_root) + sum, ans);
			}
			main_root = remove(main_root, levels[i].a, levels[i].id);
			Node q1 = new Node(levels[i].b - levels[i].a, levels[i].id, 2);
			main_root = insert(q1);
			sum += levels[i].a;
			cnt++;
		}
		if (w - cnt <= main_root.size) {
			ans = Math.min(get_sum(Math.max(w - cnt, 0), main_root) + sum, ans);
		}
		out.println(ans);
		for (int i = 0; i < Math.min(w, n); i++) {
			main_root = remove(main_root, levels[i].b - levels[i].a,
					levels[i].id);
		}
		for (int i = Math.min(w, n); i < n; i++) {
			main_root = remove(main_root, levels[i].a, levels[i].id);
		}
		answ = new int[n];
		boolean flag = false;
		long ans1 = Long.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			main_root = insert(new Node(levels[i].a, levels[i].id, 1));
		}
		sum = 0;
		cnt = 0;
		for (int i = 0; i < Math.min(w, n); i++) {
			if (main_root.size >= w - i) {
				ans1 = Math.min(get_sum(w - i, main_root) + sum, ans1);
				if ((ans1 == ans) && (!flag)) {
					get_ans(w - i, main_root);
					flag = true;
					break;
				}
			}
			answ[levels[i].id] = 1;
			main_root = remove(main_root, levels[i].a, levels[i].id);
			Node q1 = new Node(levels[i].b - levels[i].a, levels[i].id, 2);
			main_root = insert(q1);
			sum += levels[i].a;
			cnt++;
		}
		if (w - cnt <= main_root.size) {
			ans1 = Math.min(get_sum(Math.max(w - cnt, 0), main_root) + sum,
					ans1);
			if ((ans1 == ans) && (!flag)) {
				get_ans(w - cnt, main_root);
			}
		}
		for (int i = 0; i < n; i++) {
			out.print(answ[i]);
		}
	}

	public void run() {
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
	}
}