#include <bits/stdc++.h>
using namespace std;
struct node1 {
  long long A, id;
} A[410000], Suf[410000];
struct node {
  long long A, B, id;
} C[410000];
long long s[410000], n, p, i, An, Cn, ans, w, preA[410000], Pre[410000],
    PreT[410000], preB[410000];
bool cmp(node1 a, node1 b) { return a.A < b.A; }
bool cmpA(node a, node b) { return a.A < b.A; }
bool cmpB(node a, node b) { return a.B < b.B; }
int main() {
  scanf("%I64d%I64d", &n, &p);
  for (i = 1; i <= n; i++) {
    long long x, y;
    scanf("%I64d%I64d", &x, &y);
    if (y > 2 * x)
      A[++An] = (node1){x, i}, A[++An] = (node1){y - x, i};
    else
      C[++Cn] = (node){x, y, i};
  }
  Suf[Cn + 1] = (node1){9999999999999999LL, 0};
  sort(C + 1, C + Cn + 1, cmpB);
  sort(A + 1, A + An + 1, cmp);
  for (i = Cn; i >= 1; i--)
    if (C[i].A < Suf[i + 1].A)
      Suf[i] = (node1){C[i].A, C[i].id};
    else
      Suf[i] = Suf[i + 1];
  for (i = 1; i <= An; i++) preA[i] = preA[i - 1] + A[i].A;
  for (i = 1; i <= Cn; i++) preB[i] = preB[i - 1] + C[i].B;
  ans = 9999999999999999LL;
  long long mx = 0, mtu, pos = -1;
  for (long long i = 1; i < p - An; i++)
    if (C[i / 2 + 1].B - C[i / 2 + 1].A > mx)
      mx = C[i / 2 + 1].B - C[i / 2 + 1].A, mtu = i / 2 + 1;
  for (long long i = max(p - An, 0LL); i <= min(Cn * 2, p); i++) {
    if (i % 2 == 0)
      if (preA[p - i] + preB[i / 2] < ans)
        ans = preA[p - i] + preB[i / 2], w = i;
    if (i % 2 == 1) {
      if (C[i / 2 + 1].B - C[i / 2 + 1].A > mx)
        mx = C[i / 2 + 1].B - C[i / 2 + 1].A, mtu = i / 2 + 1;
      if (preA[p - i] + preB[i / 2] + Suf[(i / 2) + 1].A < ans)
        ans = preA[p - i] + preB[i / 2] + Suf[i / 2 + 1].A, w = i;
      if (preA[p - i] + preB[(i / 2) + 1] - mx < ans)
        ans = preA[p - i] + preB[(i / 2) + 1] - mx, w = i, pos = mtu;
    }
  }
  printf("%I64d\n", ans);
  for (int i = 1; i <= p - w; i++)
    if (s[A[i].id])
      s[A[i].id] = 2;
    else
      s[A[i].id] = 1;
  for (int i = 1; i <= w / 2; i++) s[C[i].id] = 2;
  if (w % 2 == 1)
    if (pos == -1)
      s[Suf[w / 2 + 1].id] = 1;
    else
      s[C[w / 2 + 1].id] = 2, s[C[pos].id] = 1;
  for (int i = 1; i <= n; i++) printf("%d", s[i]);
  return 0;
}
