#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)3e6;
const int N = 4194304;
int n, w;
pair<pair<int, int>, int> a[maxn];
pair<int, int> b[maxn];
int co[maxn];
int bn;
struct sta {
  int T[N * 2 + 1];
  long long sum[N * 2 + 1];
  int an;
  int a[N * 2];
  sta() { an = 0; }
  void init() {
    memset(T, 0, sizeof(T));
    memset(sum, 0, sizeof(sum));
    sort(a, a + an);
    an = unique(a, a + an) - a;
  }
  void upd(int v, int x) {
    v += N;
    T[v] += x;
    sum[v] += 1ll * x * a[v - N];
    while (v > 1) {
      v /= 2;
      T[v] = T[v + v] + T[v + v + 1];
      sum[v] = sum[v + v] + sum[v + v + 1];
    }
  }
  void add(int x, int v) {
    int p = lower_bound(a, a + an, x) - a;
    upd(p, v);
  }
  long long getSum(int n) {
    int v = 1;
    long long res = 0;
    while (true) {
      if (v >= N) {
        res += a[v - N] * n;
        break;
      }
      if (T[v + v] < n) {
        res += sum[v + v];
        n -= T[v + v];
        v += v + 1;
      } else {
        v += v;
      }
    }
    return res;
  }
} T;
long long ans;
void go(bool print = false) {
  T.init();
  for (int i = 0; i < n; ++i) T.add(a[i].first.second, 1);
  long long sum = 0;
  for (int i = 0; i <= n; ++i) {
    if (i > w) break;
    int y = a[i].first.first, x = a[i].first.second;
    if (n + i >= w) {
      if (print && ans == sum + T.getSum(w - i)) {
        int bn = 0;
        for (int j = 0; j < i; ++j) {
          b[bn++] =
              make_pair(a[j].first.first - a[j].first.second, a[j].second);
          co[a[j].second] = 1;
        }
        for (int j = i; j < n; ++j)
          b[bn++] = make_pair(a[j].first.second, a[j].second);
        sort(b, b + bn);
        for (int j = 0; j < w - i; ++j) co[b[j].second]++;
        for (int j = 0; j < n; ++j) cout << co[j];
        cout << endl;
        return;
      }
      ans = min(ans, sum + T.getSum(w - i));
    }
    if (i == n) break;
    T.add(x, -1);
    T.add(y - x, 1);
    sum += x;
  }
  cout << ans << endl;
}
int main() {
  scanf("%d%d", &n, &w);
  for (int i = 0; i < n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[i] = make_pair(make_pair(y, x), i);
    T.a[T.an++] = x;
    T.a[T.an++] = y - x;
  }
  sort(a, a + n);
  ans = (1ll << 62);
  go();
  go(true);
  return 0;
}
