#include <bits/stdc++.h>
using namespace std;
vector<pair<pair<int, int>, pair<int, int> > > by;
vector<pair<int, int> > Bn, Sn;
int n, m, w;
multiset<int> bigs, sms;
long long bn[300005], sn[300005];
int pb[300005], ps[300005];
long long bC[300005], sC[300005];
long long ans;
int point, ad;
int way[300005];
void modify(long long a[], int x, int dx, int up) {
  for (x++; x < up; x += x & (-x)) a[x] += dx;
}
long long getsum(long long a[], int x) {
  long long res = 0;
  for (x++; x; x -= x & (-x)) res += a[x];
  return res;
}
long long figure(int s, int d, int start) {
  if (start + 1 < d || (int)by.size() - start - 1 + 2 * d < s) return -1;
  int l = 0, r = n, mk;
  while (r >= l) {
    int m = (l + r) >> 1;
    if (getsum(bn, m) >= d)
      mk = m, r = m - 1;
    else
      l = m + 1;
  }
  long long sum = getsum(bC, mk);
  l = 0, r = n;
  d = w - 2 * d;
  while (r >= l) {
    int m = (l + r) >> 1;
    if (getsum(sn, m) >= d)
      mk = m, r = m - 1;
    else
      l = m + 1;
  }
  sum += getsum(sC, mk);
  return sum;
}
void bigdel(int k) {
  bigs.erase(bigs.find(by[k].second.second));
  modify(bn, pb[k], -1, n + 2);
  modify(bC, pb[k], -by[k].second.second, n + 2);
}
void sminsert(int k) {
  sms.insert(by[k].second.first);
  modify(sn, ps[k], 1, n + 2);
  modify(sC, ps[k], by[k].second.first, n + 2);
}
int main() {
  scanf("%d%d", &n, &w);
  for (int i = 1; i <= n; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    by.push_back(pair<pair<int, int>, pair<int, int> >(pair<int, int>(b - a, i),
                                                       pair<int, int>(a, b)));
    ans += b;
  }
  sort(by.begin(), by.end());
  for (int i = 0; i < by.size(); i++) {
    Sn.push_back(pair<int, int>(by[i].second.first, i));
    Bn.push_back(pair<int, int>(by[i].second.second, i));
  }
  sort(Bn.begin(), Bn.end());
  for (int i = 0; i < Bn.size(); i++) pb[Bn[i].second] = i;
  sort(Sn.begin(), Sn.end());
  for (int i = 0; i < Sn.size(); i++) ps[Sn[i].second] = i;
  for (int i = 0; i < by.size(); i++) {
    bigs.insert(by[i].second.second);
    modify(bn, pb[i], 1, n + 2);
    modify(bC, pb[i], by[i].second.second, n + 2);
  }
  int start = by.size() - 1, doub = w >> 1;
  for (int i = start; i >= -1; i--) {
    int tmp = doub;
    long long t1 = figure(w, tmp - 1, i);
    long long t2 = figure(w, tmp, i);
    if (t1 > 0 && t1 <= ans) ans = t1, doub = tmp - 1, point = i;
    if (t2 > 0 && t2 <= ans) ans = t2, doub = tmp, point = i;
    if (i >= 0) {
      bigdel(i);
      sminsert(i);
    }
  }
  cout << ans << endl;
  Bn.clear();
  for (int i = 0; i <= point; i++)
    Bn.push_back(pair<int, int>(by[i].second.second, by[i].first.second));
  sort(Bn.begin(), Bn.end());
  for (int i = 0; i < doub; i++) way[Bn[i].second] = 2;
  Bn.clear();
  for (int i = point + 1; i < by.size(); i++)
    Bn.push_back(pair<int, int>(by[i].second.first, by[i].first.second));
  sort(Bn.begin(), Bn.end());
  for (int i = 0; i < w - 2 * doub; i++) way[Bn[i].second] = 1;
  for (int i = 1; i <= n; i++) cout << way[i];
  cout << endl;
  return 0;
}
