#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n, m, a[N], b[N], vis[N];
long long ans;
struct kai {
  long long v;
  int id, t;
  kai(long long _v = 0, int _id = 0, int _t = 0) : v(_v), id(_id), t(_t) {}
};
inline bool operator<(kai a, kai b) { return a.v > b.v; }
struct sbchc {
  priority_queue<kai> q;
  kai top() {
    while (!q.empty() && vis[q.top().id] != q.top().t) q.pop();
    return q.empty() ? kai(1e18) : q.top();
  }
  void push(int v, int id, int t) { q.push(kai(v, id, t)); }
  void pop() { q.pop(); }
} q1, q2, q3;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (n); ++i)
    scanf("%d%d", a + i, b + i), q1.push(a[i], i, 0), q2.push(b[i], i, 0);
  for (int i = (1); i <= (m); ++i) {
    long long x1 = q1.top().v, x2 = q2.top().v + q3.top().v;
    if (x1 < x2) {
      ans += x1;
      auto i = q1.top().id;
      q1.pop();
      vis[i]++;
      if (vis[i] == 1)
        q1.push(b[i] - a[i], i, 1), q3.push(-a[i], i, 1);
      else
        q3.push(a[i] - b[i], i, 2);
    } else {
      ans += x2;
      auto i = q2.top().id, j = q3.top().id;
      vis[i] = 2;
      vis[j]--;
      q3.push(a[i] - b[i], i, 2);
      if (vis[j] == 1)
        q1.push(b[j] - a[j], j, 1), q3.push(-a[j], j, 1);
      else
        q1.push(a[j], j, 0), q2.push(b[j], j, 0);
    }
  }
  printf("%lld\n", ans);
  for (int i = (1); i <= (n); ++i) putchar(vis[i] + 48);
  return 0;
}
