#include <bits/stdc++.h>
using namespace std;
void Max(long long &x, long long y) { x = max(x, y); }
void Min(long long &x, long long y) { x = min(x, y); }
const long long N = 6e5 + 5;
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &a) {
  return os << '(' << a.first << ", " << a.second << ')';
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) {
  os << '[';
  for (unsigned long long i = 0; i < a.size(); i++)
    os << a[i] << (i < a.size() - 1 ? ", " : "");
  os << ']';
  return os;
}
struct Dual {
  long long first, second, id;
  Dual(long long _fi, long long _se, long long _id)
      : first(_fi), second(_se), id(_id){};
};
long long n, need;
vector<pair<long long, long long> > single;
vector<Dual> dual;
long long f[N], g[N];
const long long INF = 1e18;
void prepF() {
  fill(f, f + N, INF);
  f[0] = 0;
  for (signed i = (1); i <= (single.size()); i++)
    f[i] = f[i - 1] + single[i - 1].first;
}
void prepG() {
  fill(g, g + N, INF);
  g[0] = 0;
  multiset<pair<long long, long long> > mst, mst2;
  for (signed i = (0); i <= (dual.size() - 1); i++)
    mst.insert(make_pair(dual[i].second - dual[i].first, i));
  long long sum = 0;
  for (signed i = (0); i <= (dual.size() - 1); i++) sum += dual[i].second;
  for (signed i = (dual.size() * 2); i >= (1); i--) {
    if (i % 2 == 0) {
      g[i] = sum;
      continue;
    } else {
      long long wh = mst.rbegin()->second;
      g[i] = sum - dual[wh].second + dual[wh].first;
      long long p = (i + 1) / 2 - 1;
      mst.erase(make_pair(dual[p].second - dual[p].first, p));
      sum -= dual[p].second;
      mst2.insert(make_pair(dual[p].first, p));
      g[i] = min(g[i], sum + mst2.begin()->first);
    }
  }
}
long long status[N];
void traceF(long long X) {
  for (signed i = (1); i <= (X); i++) status[single[i - 1].second]++;
}
void traceG(long long X) {
  fill(g, g + N, INF);
  g[0] = 0;
  multiset<pair<long long, long long> > mst, mst2;
  for (signed i = (0); i <= (dual.size() - 1); i++)
    mst.insert(make_pair(dual[i].second - dual[i].first, i));
  long long sum = 0;
  for (signed i = (0); i <= (dual.size() - 1); i++) sum += dual[i].second;
  for (signed i = (dual.size() * 2); i >= (1); i--) {
    if (i % 2 == 0) {
      if (i == X) {
        for (signed j = (0); j <= (i / 2 - 1); j++) status[dual[j].id] = 2;
        break;
      }
      g[i] = sum;
      continue;
    } else {
      bool sec = false;
      long long wh = mst.rbegin()->second;
      g[i] = sum - dual[wh].second + dual[wh].first;
      long long p = (i + 1) / 2 - 1;
      mst.erase(make_pair(dual[p].second - dual[p].first, p));
      sum -= dual[p].second;
      mst2.insert(make_pair(dual[p].first, p));
      if (sum + mst2.begin()->first < g[i]) {
        sec = true;
        g[i] = sum + mst2.begin()->first;
        wh = mst2.begin()->second;
      }
      if (i == X) {
        if (!sec) {
          for (signed j = (0); j <= (p); j++) status[dual[j].id] = 2;
          status[dual[wh].id]--;
        } else {
          for (signed j = (0); j <= (p - 1); j++) status[dual[j].id] = 2;
          status[dual[wh].id]++;
        }
      }
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> need;
  for (signed i = (1); i <= (n); i++) {
    long long x, y;
    cin >> x >> y;
    if (y - x <= x)
      dual.push_back(Dual(x, y, i - 1));
    else
      single.push_back(make_pair(x, i - 1)),
          single.push_back(make_pair(y - x, i - 1));
  }
  sort(single.begin(), single.end());
  sort(dual.begin(), dual.end(),
       [&](Dual X, Dual Y) { return X.second < Y.second; });
  prepF();
  prepG();
  pair<long long, long long> ans = make_pair(INF, -1);
  for (signed i = (0); i <= (need); i++)
    ans = min(ans, make_pair(f[i] + g[need - i], (long long)i));
  cout << ans.first << '\n';
  traceF(ans.second);
  traceG(need - ans.second);
  for (signed i = (0); i <= (n - 1); i++) cout << status[i];
  cout << '\n';
}
