#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300050;
const long long mod = 1e9 + 7;
long long n, m, ans, a[MAXN], b[MAXN], stt[MAXN];
priority_queue<pair<long long, long long>, vector<pair<long long, long long> >,
               greater<pair<long long, long long> > >
    Q01, Q12, Q10, Q21, Q02;
int main() {
  cin >> n >> m;
  for (long long i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
    Q01.push({a[i], i});
    Q02.push({b[i], i});
  }
  for (long long i = 1; i <= m; i++) {
    while (!Q01.empty() && stt[Q01.top().second] != 0) Q01.pop();
    while (!Q12.empty() && stt[Q12.top().second] != 1) Q12.pop();
    while (!Q10.empty() && stt[Q10.top().second] != 1) Q10.pop();
    while (!Q21.empty() && stt[Q21.top().second] != 2) Q21.pop();
    while (!Q02.empty() && stt[Q02.top().second] != 0) Q02.pop();
    long long mn = 1e10, type;
    if (!Q01.empty() && Q01.top().first < mn) {
      mn = Q01.top().first;
      type = 1;
    }
    if (!Q12.empty() && Q12.top().first < mn) {
      mn = Q12.top().first;
      type = 2;
    }
    if (!Q10.empty() && !Q02.empty() &&
        Q10.top().first + Q02.top().first < mn) {
      mn = Q10.top().first + Q02.top().first;
      type = 3;
    }
    if (!Q21.empty() && !Q02.empty() &&
        Q21.top().first + Q02.top().first < mn) {
      mn = Q21.top().first + Q02.top().first;
      type = 4;
    }
    if (type == 1) {
      ans += mn;
      stt[Q01.top().second] = 1;
      Q10.push({-a[Q01.top().second], Q01.top().second});
      Q12.push({b[Q01.top().second] - a[Q01.top().second], Q01.top().second});
      Q01.pop();
    } else if (type == 2) {
      ans += mn;
      stt[Q12.top().second] = 2;
      Q21.push({a[Q12.top().second] - b[Q12.top().second], Q12.top().second});
      Q12.pop();
    } else if (type == 3) {
      ans += mn;
      stt[Q02.top().second] = 2;
      Q21.push({a[Q02.top().second] - b[Q02.top().second], Q02.top().second});
      Q02.pop();
      stt[Q10.top().second] = 0;
      Q01.push({a[Q10.top().second], Q10.top().second});
      Q02.push({b[Q10.top().second], Q10.top().second});
      Q10.pop();
    } else if (type == 4) {
      ans += mn;
      stt[Q21.top().second] = 1;
      Q10.push({-a[Q21.top().second], Q21.top().second});
      Q12.push({b[Q21.top().second] - a[Q21.top().second], Q21.top().second});
      Q21.pop();
      stt[Q02.top().second] = 2;
      Q21.push({a[Q02.top().second] - b[Q02.top().second], Q02.top().second});
      Q02.pop();
    }
  }
  cout << ans << endl;
  for (long long i = 1; i <= n; i++) cout << stt[i];
  return 0;
}
