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.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class C {
	static class Struct {
		int time1, time2, idx;

		public Struct(int t1, int t2, int i) {
			this.time1 = t1;
			this.time2 = t2;
			this.idx = i;
		}
	}

	static class SortingStruct implements Comparable<SortingStruct> {
		int attachedIdx, val;
		int type; // 0 means times1, 1 means times2-times1
		int sortedIdx;
		public SortingStruct(int a, int v, int t, int s) {
			attachedIdx = a;
			val = v;
			type = t;
			sortedIdx=s;
		}

		public int compareTo(SortingStruct s) {
			if (val != s.val) {
				return new Integer(val).compareTo(s.val);
			} else if (type != s.type) {
				return new Integer(type).compareTo(s.type);
			}
			return new Integer(attachedIdx).compareTo(s.attachedIdx);
		}

		public boolean equals(Object o) {
			SortingStruct s = (SortingStruct) o;
			return s.attachedIdx == attachedIdx && s.val == val
					&& s.type == type;
		}

		public int hashCode() {
			return val * 101 + attachedIdx * 103 + type;
		}
	}

	public static void main(String[] args) throws Exception {
		int n = nextInt();
		int w = nextInt();
		Struct[] ar = new Struct[n];
		for (int i = 0; i < n; i++) {
			ar[i] = new Struct(nextInt(), nextInt(), i);
		}
		Arrays.sort(ar, new Comparator<Struct>() {
			public int compare(Struct s1, Struct s2) {
				return new Integer(s1.time2).compareTo(s2.time2);
			}
		});
		TreeSet<SortingStruct> allVals = new TreeSet<>();
		for (int i = 0; i < ar.length; i++) {
			allVals.add(new SortingStruct(ar[i].idx, ar[i].time1, 0,i));
			allVals.add(new SortingStruct(ar[i].idx, ar[i].time2 - ar[i].time1,
					1,i));
		}
		HashMap<SortingStruct, Integer> map = new HashMap<>();
		HashMap<Integer, SortingStruct> revMap = new HashMap<>();
		for (SortingStruct i : allVals) {
			map.put(i, map.size() + 1);
			revMap.put(map.size(), i);
		}
		BIT vals = new BIT(map.size());
		BIT indices = new BIT(map.size());
		for (int i = 0; i < ar.length; i++) {
			SortingStruct tmp = new SortingStruct(ar[i].idx, ar[i].time1, 0,i);
			vals.update(map.get(tmp), ar[i].time1);
			indices.update(map.get(tmp), 1);
		}
		int neededIdx = indices.findIdxWithCumFreq(w);
		long res = Long.MAX_VALUE;
		int resIdx = -1,resI =-1;
		if (neededIdx != -1) {
			res = vals.getCumulativeFreq(neededIdx);
			resIdx = neededIdx;
			resI=-1;
		}
		long sumTimes1 = 0;
		for (int i = 0; i < n; i++) {
			sumTimes1 += ar[i].time1;
			long tmp = sumTimes1;
			SortingStruct ss = new SortingStruct(ar[i].idx, ar[i].time1, 0,i);
			indices.update(map.get(ss), -1);
			vals.update(map.get(ss), -ar[i].time1);
			ss = new SortingStruct(ar[i].idx, ar[i].time2 - ar[i].time1, 1,i);
			indices.update(map.get(ss), 1);
			vals.update(map.get(ss), ar[i].time2 - ar[i].time1);
			neededIdx = indices.findIdxWithCumFreq(w - i - 1);
			if (neededIdx != -1) {
				tmp += vals.getCumulativeFreq(neededIdx);
				if (tmp < res) {
					res=tmp;
					resIdx = neededIdx;
					resI=i;
				}
			}
		}
		int[] print=new int[n];
		for(int j=0;j<=resI;j++){
			print[ar[j].idx]=1;
		}
		for(int i=1;i<=resIdx;i++) {
			SortingStruct ss=revMap.get(i);
			if(ss.type==0 && ss.sortedIdx>resI){
				print[ss.attachedIdx]=1;
			}else if(ss.type==1&&ss.sortedIdx<=resI){
				print[ss.attachedIdx]=2;
			}
		}
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<print.length;i++){
			sb.append(print[i]);
		}
		System.out.println(res);
		System.out.println(sb);
	}

	static class BIT {
		long[] BIT; // length should be 1+maxVal

		public BIT(int n) {
			BIT = new long[n + 1];
		}

		public long getCumulativeFreq(int idx) {
			long res = 0;
			while (idx > 0) {
				res += BIT[idx];
				idx -= (idx & -idx);
			}
			return res;
		}

		public long getFreq(int idx) {
			long res = BIT[idx];
			int end = idx - (idx & -idx);
			idx--;
			while (idx > end) {
				res -= BIT[idx];
				idx -= (idx & -idx);
			}
			return res;
		}

		public void update(int idx, long val) {
			while (idx < BIT.length) {
				BIT[idx] += val;
				idx += (idx & -idx);
			}
		}

		public int findIdxWithCumFreq(int freq) {
			int l = 1, h = BIT.length, mid;
			while (l < h) {
				mid = l + (h - l) / 2;
				long tmp = getCumulativeFreq(mid);
				if (tmp < freq) {
					l = mid + 1;
				} else {
					h = mid;
				}
			}
			if (l == BIT.length)
				return -1;
			return l;
		}
	}

	static BufferedReader br = new BufferedReader(new InputStreamReader(
			System.in));
	static StringTokenizer tokenizer = new StringTokenizer("");

	static int nextInt() throws Exception {
		return Integer.parseInt(next());
	}

	static double nextDouble() throws Exception {
		return Double.parseDouble(next());
	}

	static String next() throws Exception {
		while (true) {
			if (tokenizer.hasMoreTokens()) {
				return tokenizer.nextToken();
			}
			String s = br.readLine();
			if (s == null) {
				return null;
			}
			tokenizer = new StringTokenizer(s);
		}
	}
}