#include <bits/stdc++.h>
using namespace std;
int n, m, w, a[600005], b[600005], c[600005], idc[600005], pdc[600005],
    pda[600005], ida[600005], tg[600005], mx[600005];
bool cmp1(const int &u, const int &v) { return c[u] < c[v]; }
bool cmp2(const int &u, const int &v) { return b[u] < b[v]; }
int main() {
  scanf("%d%d", &n, &w);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &a[i], &b[i]);
    if (b[i] - a[i] >= a[i]) {
      c[++c[0]] = a[i], pdc[c[0]] = i;
      c[++c[0]] = b[i] - a[i], pdc[c[0]] = i;
    } else {
      pda[++m] = i;
      a[m] = a[i], b[m] = b[i];
    }
  }
  for (int i = 1; i <= c[0]; i++) idc[i] = i;
  for (int i = 1; i <= m; i++) ida[i] = i;
  sort(idc + 1, idc + 1 + c[0], cmp1);
  sort(ida + 1, ida + 1 + m, cmp2);
  long long ans = 0x3f3f3f3f3f3f3f3fll, lc = 0, la = 0, lm = 0, lq = 0, sum = 0,
            mxa = 0, j = m;
  for (int i = 1; i <= m; i++) {
    sum += b[i];
    if (i == 1)
      mx[i] = ida[1];
    else
      mx[i] = b[ida[i]] - a[ida[i]] > b[mx[i - 1]] - a[mx[i - 1]] ? ida[i]
                                                                  : mx[i - 1];
  }
  for (int i = 0; i <= c[0]; i++) {
    for (; j >= 0 && j * 2 + i > w; j--) {
      sum -= b[ida[j]];
      if (mxa == 0 || a[ida[j]] < a[mxa]) mxa = ida[j];
    }
    if (j < 0) break;
    if (j * 2 + i == w) {
      if (sum < ans) ans = sum, lc = i, la = j, lm = 0, lq = 0;
    } else if (j * 2 + i + 1 == w) {
      if (mxa && sum + a[mxa] < ans) {
        ans = sum + a[mxa], lc = i, la = j, lm = mxa, lq = 0;
      }
      if (j < m && mx[j + 1] &&
          sum + b[ida[j + 1]] - b[mx[j + 1]] + a[mx[j + 1]] < ans)
        ans = sum + b[ida[j + 1]] - b[mx[j + 1]] + a[mx[j + 1]], lc = i,
        la = j + 1, lm = 0, lq = mx[j + 1];
    }
    sum += c[idc[i + 1]];
  }
  printf("%lld\n", ans);
  for (int i = 1; i <= lc; i++) tg[pdc[idc[i]]]++;
  for (int i = 1; i <= la; i++) tg[pda[ida[i]]] += 2;
  if (lm) tg[pda[lm]]++;
  if (lq) tg[pda[lq]]--;
  for (int i = 1; i <= n; i++) printf("%d", tg[i]);
}
