#include <bits/stdc++.h>
using namespace std;
namespace IO {
inline char ch() {
  static char s[1 << 16], *S, *T;
  return (S == T) && (T = (S = s) + fread(s, 1, 1 << 16, stdin), S == T) ? EOF
                                                                         : *S++;
}
template <typename T>
void read(T &x) {
  x = 0;
  int f(1);
  char c = ch();
  for (; !isdigit(c); c = ch())
    if (c == '-') f = -1;
  for (; isdigit(c); c = ch()) x = x * 10 + c - '0';
  x *= f;
}
}  // namespace IO
using namespace IO;
const int maxn = 300005;
const int saxn = 10000003;
const long long inf = 1000000000;
int n, m, Rt;
int state[maxn];
struct Level {
  long long a, b;
  int id;
  Level(long long ta = 0, long long tb = 0, int ti = 0)
      : a(ta), b(tb), id(ti) {}
  bool operator<(const Level &o) const { return b < o.b; }
} A[maxn];
long long Ans;
struct node {
  int id;
  long long vl;
  bool operator<(const node &o) const { return vl > o.vl; }
};
priority_queue<node> hp;
struct segment_tree {
  int sum[saxn], tot;
  long long vls[saxn];
  int lc[saxn], rc[saxn];
  void Modify(int &now, long long l, long long r, long long pos, int vl) {
    if (!now) now = ++tot;
    sum[now] += vl;
    vls[now] += pos * vl;
    if (l == r) return;
    if (pos <= ((l + r) >> 1))
      Modify(lc[now], l, ((l + r) >> 1), pos, vl);
    else
      Modify(rc[now], ((l + r) >> 1) + 1, r, pos, vl);
  }
  long long Query(int now, long long l, long long r, int K) {
    if (K <= 0) return 0;
    if (sum[now] < K) return 1e16;
    if (l == r) return K * l;
    if (!now) return 0;
    if (sum[lc[now]] < K)
      return vls[lc[now]] +
             Query(rc[now], ((l + r) >> 1) + 1, r, K - sum[lc[now]]);
    else
      return Query(lc[now], l, ((l + r) >> 1), K);
  }
} seg;
int main() {
  read(n);
  read(m);
  for (int i(1); i <= n; ++i) {
    read(A[i].a);
    read(A[i].b);
    A[i].id = i;
  }
  sort(A + 1, A + 1 + n);
  for (int i(1); i <= n; ++i) seg.Modify(Rt, 0, inf, A[i].a, 1);
  Ans = seg.Query(Rt, 0, inf, m);
  seg.Modify(Rt, 0, inf, A[1].a, -1);
  long long sum = 0;
  int pos = 0;
  for (int i(1); i <= n; ++i) {
    long long nowans = sum + A[i].b + seg.Query(1, 0, inf, m - i - 1);
    if (Ans > nowans) Ans = nowans, pos = i;
    sum += A[i].a;
    seg.Modify(Rt, 0, inf, A[i].b - A[i].a, 1);
    if (i < n) seg.Modify(Rt, 0, inf, A[i + 1].a, -1);
  }
  printf("%lld\n", Ans);
  for (int i(1); i <= n; ++i)
    if (i < pos)
      hp.push((node){i, A[i].b - A[i].a});
    else if (i > pos)
      hp.push((node){i, A[i].a});
  m = m - pos - 1 + (pos == 0);
  for (int i(1); i < pos; ++i) state[A[i].id] = 1;
  if (pos) state[A[pos].id] = 2;
  while (m--) {
    node u = hp.top();
    hp.pop();
    if (u.id < pos)
      state[A[u.id].id] = 2;
    else
      state[A[u.id].id] = 1;
  }
  for (int i(1); i <= n; ++i) printf("%d", state[i]);
  puts("");
  return 0;
}
