#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<long long, long long>, vector<pair<long long, long long> >,
               greater<pair<long long, long long> > >
    a1, a2, a3, a4, a5;
long long a[300005], b[300005];
long long h[300005];
signed main() {
  long long n, w, ans = 0;
  scanf("%lld%lld", &n, &w);
  for (register long long i = 1; i <= n; i++) {
    scanf("%lld%lld", &a[i], &b[i]);
    a1.push(make_pair(a[i], i)), a4.push(make_pair(b[i], i));
  }
  while (w--) {
    long long Min = 1e18, op, p, q;
    while (!a1.empty() && h[a1.top().second] != 0) a1.pop();
    while (!a2.empty() && h[a2.top().second] != 1) a2.pop();
    while (!a3.empty() && h[a3.top().second] != 1) a3.pop();
    while (!a4.empty() && h[a4.top().second] != 0) a4.pop();
    while (!a5.empty() && h[a5.top().second] != 2) a5.pop();
    if (!a1.empty() && a1.top().first < Min)
      Min = a1.top().first, p = a1.top().second, op = 1;
    if (!a2.empty() && a2.top().first < Min)
      Min = a2.top().first, p = a2.top().second, op = 2;
    if (!a4.empty() && !a3.empty() && a3.top().first + a4.top().first < Min)
      Min = a3.top().first + a4.top().first, p = a4.top().second,
      q = a3.top().second, op = 3;
    if (!a4.empty() && !a5.empty() && a4.top().first + a5.top().first < Min)
      Min = a4.top().first + a5.top().first, p = a4.top().second,
      q = a5.top().second, op = 4;
    ans += Min;
    if (op == 1)
      a1.pop(), a2.push(make_pair(b[p] - a[p], p)),
          a3.push(make_pair(-a[p], p)), h[p] = 1;
    if (op == 2) a2.pop(), a5.push(make_pair(a[p] - b[p], p)), h[p] = 2;
    if (op == 3)
      a4.pop(), a5.push(make_pair(a[p] - b[p], p)), a1.push(make_pair(a[q], q)),
          a4.push(make_pair(b[q], q)), h[p] = 2, h[q] = 0;
    if (op == 4)
      a4.pop(), a5.push(make_pair(a[p] - b[p], p)),
          a2.push(make_pair(b[q] - a[q], q)), a3.push(make_pair(-a[q], q)),
          h[p] = 2, h[q] = 1;
  }
  cout << ans << '\n';
  for (register long long i = 1; i <= n; i++) {
    putchar(h[i] + '0');
  }
  putchar('\n');
  return 0;
}
