#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != '-') ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
  return x * f;
}
inline void print(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x / 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int N = 3e5 + 5;
int n, m, b[N];
long long ans;
struct node {
  int x, y, id;
} a[N];
struct node1 {
  int x, y, id;
  inline bool operator<(const node1 &hh) const { return x > hh.x; }
};
priority_queue<node1> q1;
struct node2 {
  int x, y, id;
  inline bool operator<(const node2 &hh) const { return x < hh.x; }
};
priority_queue<node2> q2;
struct node3 {
  int x, y, id;
  inline bool operator<(const node3 &hh) const {
    return (y - x) > (hh.y - hh.x);
  }
};
priority_queue<node3> q3;
struct node4 {
  int x, y, id;
  inline bool operator<(const node4 &hh) const {
    return (y - x) < (hh.y - hh.x);
  }
};
priority_queue<node4> q4;
struct node5 {
  int x, y, id;
  inline bool operator<(const node5 &hh) const { return y > hh.y; }
};
priority_queue<node5> q5;
signed main() {
  n = read();
  m = read();
  for (register int i = 1; i <= n; i++) {
    a[i].x = read();
    a[i].y = read();
    a[i].id = i;
    q1.push((node1){a[i].x, a[i].y, i});
    q5.push((node5){a[i].x, a[i].y, i});
  }
  for (register int i = 1; i <= m; i++) {
    int t1, t2, t3, t4;
    t1 = t2 = t3 = t4 = 1e9 + 5;
    while (!q1.empty() && b[q1.top().id] != 0) q1.pop();
    while (!q2.empty() && b[q2.top().id] != 1) q2.pop();
    while (!q3.empty() && b[q3.top().id] != 1) q3.pop();
    while (!q4.empty() && b[q4.top().id] != 2) q4.pop();
    while (!q5.empty() && b[q5.top().id] != 0) q5.pop();
    if (!q1.empty()) t1 = q1.top().x;
    if (!q3.empty()) t2 = q3.top().y - q3.top().x;
    if (!q5.empty() && !q2.empty()) t3 = q5.top().y - q2.top().x;
    if (!q5.empty() && !q4.empty()) t4 = q5.top().y - (q4.top().y - q4.top().x);
    if (t1 <= t2 && t1 <= t3 && t1 <= t4) {
      node1 tmp = q1.top();
      q1.pop();
      ans += (long long)t1;
      b[tmp.id] = 1;
      q2.push((node2){tmp.x, tmp.y, tmp.id});
      q3.push((node3){tmp.x, tmp.y, tmp.id});
      continue;
    }
    if (t2 <= t1 && t2 <= t3 && t2 <= t4) {
      node3 tmp = q3.top();
      q3.pop();
      ans += (long long)t2;
      b[tmp.id] = 2;
      q4.push((node4){tmp.x, tmp.y, tmp.id});
      continue;
    }
    if (t3 <= t1 && t3 <= t2 && t3 <= t4) {
      node5 tmp1 = q5.top();
      q5.pop();
      node2 tmp2 = q2.top();
      q2.pop();
      ans += (long long)t3;
      b[tmp1.id] = 2;
      b[tmp2.id] = 0;
      q4.push((node4){tmp1.x, tmp1.y, tmp1.id});
      q1.push((node1){tmp2.x, tmp2.y, tmp2.id});
      q5.push((node5){tmp2.x, tmp2.y, tmp2.id});
      continue;
    }
    if (t4 <= t1 && t4 <= t2 && t4 <= t3) {
      node5 tmp1 = q5.top();
      q5.pop();
      node4 tmp2 = q4.top();
      q4.pop();
      ans += (long long)t4;
      b[tmp1.id] = 2;
      b[tmp2.id] = 1;
      q4.push((node4){tmp1.x, tmp1.y, tmp1.id});
      q2.push((node2){tmp2.x, tmp2.y, tmp2.id});
      q3.push((node3){tmp2.x, tmp2.y, tmp2.id});
    }
  }
  print(ans);
  putchar('\n');
  for (register int i = 1; i <= n; i++) print(b[i]);
  return 0;
}
