#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const int MAXN = 3e5 + 5;
int n, m, a[MAXN], b[MAXN], star[MAXN];
priority_queue<pair<long long, int>, vector<pair<long long, int> >,
               greater<pair<long long, int> > >
    q1, q2, q3, q4, q5;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
  q1.push(make_pair(INF, n + 1));
  q2.push(make_pair(INF, n + 1));
  q3.push(make_pair(INF, n + 1));
  q4.push(make_pair(INF, n + 1));
  q5.push(make_pair(INF, n + 1));
  star[n + 1] = -1;
  for (int i = 1; i <= n; i++)
    q1.push(make_pair(a[i], i)), q3.push(make_pair(b[i], i));
  long long ans = 0;
  for (int i = 1; i <= m; i++) {
    while (q1.size() > 1 && star[q1.top().second] != 0) q1.pop();
    while (q2.size() > 1 && star[q2.top().second] != 1) q2.pop();
    while (q3.size() > 1 && star[q3.top().second] != 0) q3.pop();
    while (q4.size() > 1 && star[q4.top().second] != 1) q4.pop();
    while (q5.size() > 1 && star[q5.top().second] != 2) q5.pop();
    long long x1 = q1.top().first, x2 = q2.top().first,
              x3 = q3.top().first + q4.top().first,
              x4 = q3.top().first + q5.top().first;
    long long mn = min(min(x1, x2), min(x3, x4));
    ans += mn;
    if (x1 == mn) {
      int j = q1.top().second;
      star[j] = 1;
      q1.pop();
      q2.push(make_pair(b[j] - a[j], j));
      q4.push(make_pair(-a[j], j));
    } else if (x2 == mn) {
      int j = q2.top().second;
      star[j] = 2;
      q2.pop();
      q5.push(make_pair(-b[j] + a[j], j));
    } else if (x3 == mn) {
      int j1 = q3.top().second, j2 = q4.top().second;
      star[j1] = 2;
      star[j2] = 0;
      q3.pop();
      q4.pop();
      q5.push(make_pair(-b[j1] + a[j1], j1));
      q1.push(make_pair(a[j2], j2));
      q3.push(make_pair(b[j2], j2));
    } else {
      int j1 = q3.top().second, j2 = q5.top().second;
      star[j1] = 2;
      star[j2] = 1;
      q3.pop();
      q5.pop();
      q5.push(make_pair(-b[j1] + a[j1], j1));
      q2.push(make_pair(b[j2] - a[j2], j2));
      q4.push(make_pair(-a[j2], j2));
    }
  }
  printf("%lld\n", ans);
  for (int i = 1; i <= n; i++) printf("%d", star[i]);
  return 0;
}
