#include <bits/stdc++.h>
using namespace std;
int n, m;
int b, p;
int c[300010], a1[300010], b1[300010];
long long ans;
priority_queue<pair<int, pair<int, pair<int, int> > > > q;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &b, &p);
    p -= b;
    a1[i] = b;
    b1[i] = p;
    q.push(make_pair(-(b * 2), make_pair(-p, make_pair(1, i))));
    q.push(make_pair(-(p + b), make_pair(-p, make_pair(2, i))));
  }
  int ha = 0;
  while (ha < m - 1) {
    int h = -q.top().first;
    int d = q.top().second.second.first;
    int num = q.top().second.second.second;
    int p = -q.top().second.first;
    if (c[num] == 2 || (ha == m - 1 && d == 2 && c[num] == 0)) {
      q.pop();
      continue;
    }
    if (d == 1) {
      c[num] = 1;
      h /= 2;
      ans = ans + h;
      ha++;
      q.push(make_pair(-(p * 2), make_pair(-p, make_pair(3, num))));
    }
    if (d == 2) {
      if (c[num] == 1) {
        q.pop();
        continue;
      } else {
        ha += 2;
        ans = ans + h;
      }
      c[num] = 2;
    }
    if (d == 3) {
      ans = ans + (h / 2);
      ha++;
      c[num] = 2;
    }
    q.pop();
  }
  if (ha == m - 1) {
    int c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0;
    int q1, q2, q3, q4;
    q1 = q2 = q3 = q4 = 2000000001;
    for (int i = 1; i <= n; i++)
      if (c[i] == 0) {
        if (!c5 || a1[c5] + b1[c5] > a1[i] + b1[i]) c5 = i;
        if (!c3 || a1[c3] > a1[i]) c3 = i;
      } else if (c[i] == 1) {
        if (!c1 || a1[c1] < a1[i]) c1 = i;
        if (!c4 || b1[c4] > b1[i]) c4 = i;
      } else if (c[i] == 2)
        if (!c2 || b1[c2] < b1[i]) c2 = i;
    if (c3) q1 = a1[c3];
    if (c4) q2 = b1[c4];
    if (c1 && c5) q3 = a1[c5] + b1[c5] - a1[c1];
    if (c2 && c5) q4 = a1[c5] + b1[c5] - b1[c2];
    if (q1 <= q2 && q1 <= q3 && q1 <= q4) {
      ans += a1[c3];
      c[c3] = 1;
    } else if (q2 <= q1 && q2 <= q3 && q2 <= q4) {
      ans += b1[c4];
      c[c4] = 2;
    } else if (q3 <= q2 && q3 <= q1 && q3 <= q4) {
      ans += a1[c5] + b1[c5] - a1[c1];
      c[c5] = 2;
      c[c1] = 0;
    } else if (q4 <= q2 && q4 <= q3 && q4 <= q1) {
      ans += a1[c5] + b1[c5] - b1[c2];
      c[c5] = 2;
      c[c2] = 1;
    }
  }
  printf("%lld\n", ans);
  for (int i = 1; i <= n; i++) putchar(c[i] + 48);
  return 0;
}
