#include <bits/stdc++.h>
using namespace std;
int c[300005], n, a[300005], b[300005], m;
long long ans;
struct que {
  int op;
  priority_queue<pair<int, int> > q;
  void ins(pair<int, int> x) { q.push(x); }
  bool check() {
    while (!q.empty() && op != c[q.top().second]) q.pop();
    if (q.empty()) return true;
    return false;
  }
  pair<int, int> get() { return q.top(); }
} q[5];
int main() {
  scanf("%d%d", &n, &m);
  q[0].op = q[2].op = 0;
  q[1].op = q[3].op = 1;
  q[4].op = 2;
  for (int i = 1; i <= n; i++)
    scanf("%d%d", &a[i], &b[i]), q[0].ins(make_pair(-a[i], i)),
        q[2].ins(make_pair(-b[i], i));
  while (m--) {
    int u[5];
    u[0] = q[0].check() ? 0x7fffffff : -q[0].get().first;
    u[1] = q[1].check() ? 0x7fffffff : -q[1].get().first;
    u[2] = (q[2].check() || q[3].check())
               ? 0x7fffffff
               : -q[2].get().first - q[3].get().first;
    u[3] = (q[2].check() || q[4].check())
               ? 0x7fffffff
               : -q[2].get().first - q[4].get().first;
    if (u[0] <= u[1] && u[0] <= u[2] && u[0] <= u[3]) {
      ans += u[0];
      int now = q[0].get().second;
      c[now] = 1;
      q[1].ins(make_pair(a[now] - b[now], now));
      q[3].ins(make_pair(a[now], now));
    } else if (u[1] <= u[0] && u[1] <= u[2] && u[1] <= u[3]) {
      ans += u[1];
      int now = q[1].get().second;
      c[now] = 2;
      q[4].ins(make_pair(b[now] - a[now], now));
    } else if (u[2] <= u[0] && u[2] <= u[1] && u[2] <= u[3]) {
      ans += u[2];
      int x = q[2].get().second, y = q[3].get().second;
      c[x] = 2;
      c[y] = 0;
      q[4].ins(make_pair(b[x] - a[x], x));
      q[0].ins(make_pair(-a[y], y));
      q[2].ins(make_pair(-b[y], y));
    } else {
      ans += u[3];
      int x = q[2].get().second, y = q[4].get().second;
      c[x] = 2;
      c[y] = 1;
      q[4].ins(make_pair(b[x] - a[x], x));
      q[1].ins(make_pair(a[y] - b[y], y));
      q[3].ins(make_pair(a[y], y));
    }
  }
  printf("%lld\n", ans);
  for (int i = 1; i <= n; i++) printf("%d", c[i]);
  return 0;
}
