#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
const int T = (1 << 21) + 5;
int n, w;
int c[N + N];
int lg = 1;
int cnt[T];
long long sum[T];
int len, L;
long long ans = (1ll << 60), cur, res;
struct st {
  int a, b, ix;
} d[N + N];
bool cmp(st a, st b) { return a.b < b.b; }
bool cmp2(st a, st b) { return a.a < b.a; }
void add(int id, int val) {
  id = lower_bound(c + 1, c + len + 1, id) - c;
  id = id + lg - 1;
  cnt[id] += val;
  sum[id] += val * c[id - lg + 1];
  while (id > 1) {
    id >>= 1;
    cnt[id] = cnt[id + id] + cnt[id + id + 1];
    sum[id] = sum[id + id] + sum[id + id + 1];
  }
}
long long get(int kol) {
  int q = 0;
  if (kol == 2) q = 1;
  int v = 1;
  long long ret = 0;
  while (v < lg) {
    if (cnt[v + v] < kol)
      ret += sum[v + v], kol -= cnt[v + v], v += v + 1;
    else
      v += v;
  }
  ret += c[v - lg + 1] * kol;
  return ret;
}
int main() {
  scanf("%d%d", &n, &w);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &d[i].a, &d[i].b);
    d[i].ix = i;
    c[++len] = d[i].a;
    c[++len] = d[i].b - d[i].a;
  }
  sort(c + 1, c + len + 1);
  sort(d + 1, d + n + 1, &cmp);
  len = unique(c + 1, c + len + 1) - c - 1;
  while (lg < len) lg += lg;
  for (int i = 1; i <= n; ++i) add(d[i].a, 1);
  for (int i = 0; i <= min(n, w); ++i) {
    add(d[i].a, -1);
    add(d[i].b - d[i].a, 1);
    cur += d[i].a;
    if (n + i >= w) {
      res = cur + get(w - i);
      if (ans > res) ans = res, L = i;
    }
  }
  printf("%I64d\n", ans);
  memset(c, 0, sizeof c);
  for (int i = 1; i <= L; ++i) {
    d[i].a = d[i].b - d[i].a;
    c[d[i].ix] = 1;
  }
  sort(d + 1, d + n + 1, &cmp2);
  for (int i = 1; i <= w - L; ++i) ++c[d[i].ix];
  for (int i = 1; i <= n; ++i) printf("%d", c[i]);
  return 0;
}
