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.*;

public class E {


	public E () {
		int N = sc.nextInt();
		int W = sc.nextInt();
		int [][] T = sc.nextInts(N);

		PriorityQueue<Tuple<Integer>> Q = new PriorityQueue<>(), R = new PriorityQueue<>();
		for (int i : rep(N)) {
			Q.add(tuple(T[i][0], i, 1));
			R.add(tuple(T[i][1], i, 1, -T[i][0]));
		}

		long Z = 0; int [] res = new int [N];
		while (W > 0)
			if (W == 1) {
				Tuple<Integer> q = pick (Q, res);
				Z += q.a[0];
				res[q.a[1]] = q.a[2]; --W;
			} else {
				Tuple<Integer> q1 = pick(Q, res), q2 = pick(Q, res);
				Tuple<Integer> r = pick(R, res);
				long X = LINF, Y = LINF;
				if (q2 != null)
					X = q1.a[0] + q2.a[0];
				if (r != null)
					Y = r.a[0];

				if (X < Y) {
					Z += q1.a[0];
					int i = q1.a[1], j = q2.a[1], m = q1.a[2], n = q2.a[2];
					res[i] = m; //res[j] = n;
					if (m == 1) { q1.a[0] = T[i][1] - T[i][0]; q1.a[2] = 2; Q.add(q1); }
					//if (n == 1) { q2.a[0] = T[j][1] - T[j][0]; q2.a[2] = 2; Q.add(q2); }
					if (r != null)
						R.add(r);
					Q.add(q2);
					--W;
				} else {
					int i = r.a[1];
					Z += T[i][0];
					res[i] = 1;
					r.a[0] = T[i][1] - T[i][0]; r.a[2] = 2; Q.add(r);
					Q.add(q1);
					if (q2 != null)
						Q.add(q2);
					--W;
				}
			}

		StringBuilder S = new StringBuilder();
		for (int i : res) S.append(i);

		print(Z);
		exit(S);
	}

	Tuple<Integer> pick(PriorityQueue<Tuple<Integer>> Q, int [] res) {
		while (!Q.isEmpty()) {
			Tuple<Integer> q = Q.poll();
			int i = q.a[1], L = q.a[2];
			if (res[i] < L)
				return q;
		}
		return null;
	}

	private static final long LINF = (long) 1e18;
	private static int [] rep(int N) { return rep(0, N); }
	private static int [] rep(int S, int T) { if (T <= S) return new int [0]; int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[i-S] = i; return res; }
	private static <T> Tuple<T> tuple (@SuppressWarnings("unchecked") T ... A) { return new Tuple<T>(A); }
	private static class Tu {
		private static class ple<T> implements Comparable<ple<T>> {
			public final T [] a;
			public ple(@SuppressWarnings("unchecked") T ... a) { this.a = a; }
			@SuppressWarnings("unchecked") public int compareTo(ple<T> o) {
				if (a.length > o.a.length)
					return -o.compareTo(this);
				for (int i = 0; i < a.length; ++i)
					if (((Comparable<T>)a[i]).compareTo(o.a[i]) != 0)
						return ((Comparable<T>)a[i]).compareTo(o.a[i]);
				return a.length - o.a.length;
			}
			@SuppressWarnings("unchecked") public boolean equals(Object o) { return Arrays.equals(a, ((ple<T>)o).a); }
			public int hashCode() { return Arrays.hashCode(a); };
			public String toString() { return Arrays.toString(a); }
		}
	}
	private static class Tuple<T> extends Tu.ple<T> { public Tuple(@SuppressWarnings("unchecked") T ... a) { super(a); }}
	////////////////////////////////////////////////////////////////////////////////////
	private final static IOUtils.MyScanner sc = new IOUtils.MyScanner();
	private static void print (Object o, Object ... A) { IOUtils.print(o, A); }
	private static void exit (Object o, Object ... A) { IOUtils.print(o, A); IOUtils.exit(); }
	private static class IOUtils {
		public static class MyScanner {
			public String next() { newLine(); return line[index++]; }
			public int nextInt() { return Integer.parseInt(next()); }
			public String nextLine() { line = null; return readLine(); }
			public String [] nextStrings() { return split(nextLine()); }
			public int [] nextInts() {
				String [] L = nextStrings();
				int [] res = new int [L.length];
				for (int i = 0; i < L.length; ++i)
					res[i] = Integer.parseInt(L[i]);
				return res;
			}
			public int [][] nextInts (int N) {
				int [][] res = new int [N][];
				for (int i = 0; i < N; ++i)
					res[i] = nextInts();
				return res;
			}
			//////////////////////////////////////////////
			private boolean eol() { return index == line.length; }
			private String readLine() {
				try {
					return r.readLine();
				} catch (Exception e) {
					throw new Error (e);
				}
			}
			private final java.io.BufferedReader r;
			private MyScanner () { this(new java.io.BufferedReader(new java.io.InputStreamReader(System.in))); }
			private MyScanner (java.io.BufferedReader r) {
				try {
					this.r = r;
					while (!r.ready())
						Thread.sleep(1);
					start();
				} catch (Exception e) {
					throw new Error(e);
				}
			}
			private String [] line;
			private int index;
			private void newLine() {
				if (line == null || eol()) {
					line = split(readLine());
					index = 0;
				}
			}
			private String [] split(String s) { return s.length() > 0 ? s.split(" ") : new String [0]; }
		}
		private static String build(Object o, Object ... A) { return buildDelim(" ", o, A); }
		private static String buildDelim(String delim, Object o, Object ... A) {
			StringBuilder b = new StringBuilder();
			append(b, o, delim);
			for (Object p : A)
				append(b, p, delim);
			return b.substring(delim.length());
		}
		//////////////////////////////////////////////////////////////////////////////////
		private static void start() { if (t == 0) t = millis(); }
		private static void append(StringBuilder b, Object o, String delim) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					append(b, java.lang.reflect.Array.get(o, i), delim);
			} else if (o instanceof Iterable<?>)
				for (Object p : (Iterable<?>) o)
					append(b, p, delim);
			else {
				if (o instanceof Double)
					o = new java.text.DecimalFormat("#.############").format(o);
				b.append(delim).append(o);
			}
		}
		private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);
		private static void print(Object o, Object ... A) { pw.println(build(o, A)); }
		private static void err(Object o, Object ... A) { System.err.println(build(o, A)); }
		private static void exit() {
			IOUtils.pw.close();
			System.out.flush();
			err("------------------");
			err(IOUtils.time());
			System.exit(0);
		}
		private static long t;
		private static long millis() { return System.currentTimeMillis(); }
		private static String time() { return "Time: " + (millis() - t) / 1000.0; }
	}
	public static void main (String[] args) { new E(); IOUtils.exit(); }
}