#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long s = 0, w = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
  return s * w;
}
priority_queue<pair<long long, long long>, vector<pair<long long, long long> >,
               greater<pair<long long, long long> > >
    q1, q2, q3, q4, q5;
long long a[300003], b[300003], f[300003];
signed main() {
  long long n = read(), m = read();
  for (long long i = 1; i <= n; i++)
    a[i] = read(), b[i] = read(), q1.push(make_pair(a[i], i)),
    q3.push(make_pair(b[i], i));
  long long ans = 0;
  while (m--) {
    long long x = 10000000000ll, opt = -1;
    while (!q1.empty() && f[(q1.top().second)] != 0) q1.pop();
    while (!q2.empty() && f[(q2.top().second)] != 1) q2.pop();
    while (!q3.empty() && f[(q3.top().second)] != 0) q3.pop();
    while (!q4.empty() && f[(q4.top().second)] != 2) q4.pop();
    while (!q5.empty() && f[(q5.top().second)] != 1) q5.pop();
    if (!q1.empty() && (q1.top().first) < x) x = (q1.top().first), opt = 1;
    if (!q2.empty() && (q2.top().first) < x) x = (q2.top().first), opt = 2;
    if (!q3.empty() && !q4.empty() && (q3.top().first) + (q4.top().first) < x)
      x = (q3.top().first) + (q4.top().first), opt = 3;
    if (!q3.empty() && !q5.empty() && (q3.top().first) + (q5.top().first) < x)
      x = (q3.top().first) + (q5.top().first), opt = 4;
    ans += x;
    if (opt == 1)
      f[(q1.top().second)] = 1,
      q2.push(make_pair(b[(q1.top().second)] - a[(q1.top().second)],
                        (q1.top().second))),
      q5.push(make_pair(-a[(q1.top().second)], (q1.top().second))), q1.pop();
    if (opt == 2)
      f[(q2.top().second)] = 2,
      q4.push(make_pair(a[(q2.top().second)] - b[(q2.top().second)],
                        (q2.top().second))),
      q2.pop();
    if (opt == 3)
      f[(q3.top().second)] = 2, f[(q4.top().second)] = 1,
      q4.push(make_pair(a[(q3.top().second)] - b[(q3.top().second)],
                        (q3.top().second))),
      q2.push(make_pair(b[(q4.top().second)] - a[(q4.top().second)],
                        (q4.top().second))),
      q5.push(make_pair(-a[(q4.top().second)], (q4.top().second))), q3.pop(),
      q4.pop();
    if (opt == 4)
      f[(q3.top().second)] = 2, f[(q5.top().second)] = 0,
      q4.push(make_pair(a[(q3.top().second)] - b[(q3.top().second)],
                        (q3.top().second))),
      q1.push(make_pair(a[(q5.top().second)], (q5.top().second))),
      q3.push(make_pair(b[(q5.top().second)], (q5.top().second))), q3.pop(),
      q5.pop();
  }
  printf("%lld\n", ans);
  for (long long i = 1; i <= n; i++) printf("%lld", f[i]);
  puts("");
  return 0;
}
