#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
struct node {
  int id;
  long long num;
  bool operator<(const node &x) const { return num > x.num; }
};
priority_queue<node> q1, q2, q3, q4, q5;
int n, w, op1, op2 = 1, op3 = 1, op4, op5 = 2;
long long sum, a[N], b[N], ans[N];
signed main() {
  scanf("%d%d", &n, &w);
  for (int i = 1; i <= n; i++) {
    scanf("%lld%lld", &a[i], &b[i]);
    q1.push((node){i, a[i]});
    q4.push((node){i, b[i]});
  }
  for (int i = 1; i <= w; i++) {
    int op, x, y;
    long long Min = 1e15;
    while (!q1.empty() && ans[q1.top().id] != op1) q1.pop();
    while (!q2.empty() && ans[q2.top().id] != op2) q2.pop();
    while (!q3.empty() && ans[q3.top().id] != op3) q3.pop();
    while (!q4.empty() && ans[q4.top().id] != op4) q4.pop();
    while (!q5.empty() && ans[q5.top().id] != op5) q5.pop();
    if (!q1.empty() && q1.top().num < Min) {
      Min = q1.top().num;
      x = q1.top().id;
      op = 1;
    }
    if (!q2.empty() && q2.top().num < Min) {
      Min = q2.top().num;
      x = q2.top().id;
      op = 2;
    }
    if (!q3.empty() && !q4.empty() && q3.top().num + q4.top().num < Min) {
      Min = q3.top().num + q4.top().num;
      x = q3.top().id;
      y = q4.top().id;
      op = 3;
    }
    while (!q4.empty() && ans[q4.top().id] != op4) q4.pop();
    if (!q5.empty() && !q4.empty() && q5.top().num + q4.top().num < Min) {
      Min = q5.top().num + q4.top().num;
      x = q5.top().id;
      y = q4.top().id;
      op = 4;
    }
    sum += Min;
    if (op == 1) {
      ans[x] = 1;
      q2.push({x, b[x] - a[x]});
      q3.push({x, -a[x]});
    }
    if (op == 2) {
      ans[x] = 2;
      q5.push({x, a[x] - b[x]});
    }
    if (op == 3) {
      ans[x] = 0;
      ans[y] = 2;
      q1.push({x, a[x]});
      q4.push({x, b[x]});
      q5.push({y, a[y] - b[y]});
    }
    if (op == 4) {
      ans[x] = 1;
      ans[y] = 2;
      q2.push({x, b[x] - a[x]});
      q3.push({x, -a[x]});
      q5.push({y, a[y] - b[y]});
    }
  }
  printf("%lld\n", sum);
  for (int i = 1; i <= n; i++) printf("%lld", ans[i]);
  return 0;
}
