#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
int n, w, a[N], b[N];
int cur[N];
long long ans;
struct node {
  long long val;
  int pos;
  node(int P, long long V) { pos = P, val = V; }
  bool operator<(const node &C) const { return val > C.val; }
};
priority_queue<node> q[6];
const int limit[] = {0, 0, 1, 1, 2};
const int p[] = {0, 1, 4, 3, 5};
const int limit2[] = {0, 0, 0, 1, 1, 2};
int ch;
const long long INF = 1LL << 60;
long long calc(int x) {
  if (x == 1) return q[1].size() ? q[1].top().val : INF;
  if (x == 2) return q[4].size() ? q[4].top().val : INF;
  if (x == 3)
    return q[3].size() && q[2].size() ? q[3].top().val + q[2].top().val : INF;
  return q[5].size() && q[2].size() ? q[5].top().val + q[2].top().val : INF;
}
void work(int x) {
  if (x == 1) {
    int pos = q[1].top().pos;
    cur[pos] = 1;
    q[3].push(node(pos, -a[pos]));
    q[4].push(node(pos, b[pos] - a[pos]));
    return;
  }
  if (x == 2) {
    int pos = q[4].top().pos;
    cur[pos] = 2;
    q[5].push(node(pos, a[pos] - b[pos]));
    return;
  }
  if (x == 3) {
    int pos1 = q[3].top().pos, pos2 = q[2].top().pos;
    cur[pos1] = 0;
    q[1].push(node(pos1, a[pos1]));
    q[2].push(node(pos1, b[pos1]));
    cur[pos2] = 2;
    q[5].push(node(pos2, a[pos2] - b[pos2]));
    return;
  }
  if (x == 4) {
    int pos1 = q[5].top().pos, pos2 = q[2].top().pos;
    cur[pos1] = 1;
    q[3].push(node(pos1, -a[pos1]));
    q[4].push(node(pos1, b[pos1] - a[pos1]));
    cur[pos2] = 2;
    q[5].push(node(pos2, a[pos2] - b[pos2]));
    return;
  }
}
int main() {
  cin >> n >> w;
  for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
  for (int i = 1; i <= n; i++) {
    q[1].push(node(i, a[i]));
    q[2].push(node(i, b[i]));
  }
  for (int c = 1; c <= w; c++) {
    ch = -1;
    for (int i = 1; i <= 5; i++)
      while (q[i].size() && cur[q[i].top().pos] != limit2[i]) q[i].pop();
    for (int i = 1; i <= 4; i++) {
      if (q[p[i]].size() && cur[q[p[i]].top().pos] == limit[i])
        if (ch == -1 || calc(i) < calc(ch)) ch = i;
    }
    ans += calc(ch);
    work(ch);
  }
  printf("%lld\n", ans);
  for (int i = 1; i <= n; i++) printf("%d", cur[i]);
  return 0;
}
