#include <bits/stdc++.h>
using namespace std;
int N, W;
int A[300002], B[300002];
multiset<pair<int, int> > Sn, An, Bn, Un, initA, initB;
long long maxA[600002], maxB[600002];
long long best, whbest;
char R[300002];
int main() {
  cin.sync_with_stdio(false);
  cin >> N >> W;
  for (int i = 1; i <= N; ++i) cin >> A[i] >> B[i];
  for (int i = 1; i <= N; ++i)
    if (B[i] - A[i] >= A[i]) {
      Sn.insert(make_pair(A[i], i));
      Sn.insert(make_pair(B[i] - A[i], i));
    } else {
      An.insert(make_pair(A[i], i));
      Bn.insert(make_pair(B[i], i));
    }
  initA = An;
  initB = Bn;
  for (auto it = Sn.begin(); it != Sn.end(); ++it)
    maxA[++maxA[0]] = (maxA[0] == 1 ? 0 : maxA[maxA[0] - 1]) + it->first;
  while (Bn.size()) {
    auto it = An.begin();
    maxB[++maxB[0]] = (maxB[0] == 1 ? 0 : maxB[maxB[0] - 1]) + it->first;
    auto itB = Bn.begin();
    maxB[++maxB[0]] = (maxB[0] == 2 ? 0 : maxB[maxB[0] - 2]) + itB->first;
    if (!Un.empty()) {
      auto itU = Un.begin();
      maxB[maxB[0] - 1] = min(maxB[maxB[0] - 1], maxB[maxB[0]] + itU->first);
    }
    int pdel = itB->second;
    An.erase(make_pair(A[pdel], pdel));
    Bn.erase(make_pair(B[pdel], pdel));
    Un.insert(make_pair(A[pdel] - B[pdel], pdel));
  }
  best = (1LL << 60), whbest = 0;
  for (int i = 0; i <= min(maxA[0], 1LL * W); ++i)
    if (W - i <= maxB[0])
      if ((i == 0 ? 0 : maxA[i]) + (W - i == 0 ? 0 : maxB[W - i]) < best) {
        best = (i == 0 ? 0 : maxA[i]) + (W - i == 0 ? 0 : maxB[W - i]);
        whbest = i;
      }
  for (int i = 1; i <= N; ++i) R[i] = '0';
  int tA = whbest;
  for (auto it = Sn.begin(); it != Sn.end() && tA; ++it, --tA) ++R[it->second];
  An = initA;
  Bn = initB;
  Un.clear();
  int complete = (W - whbest) / 2;
  while (complete--) {
    auto itB = Bn.begin();
    int pdel = itB->second;
    R[pdel] += 2;
    An.erase(make_pair(A[pdel], pdel));
    Bn.erase(make_pair(B[pdel], pdel));
    Un.insert(make_pair(A[pdel] - B[pdel], pdel));
  }
  if ((W - whbest) & 1) {
    auto itA = An.begin();
    auto itB = Bn.begin();
    auto itU = Un.begin();
    int t1 = itA->first;
    int t2 = itB->first + itU->first;
    if (t1 < t2)
      ++R[itA->second];
    else {
      R[itB->second] += 2;
      --R[itU->second];
    }
  }
  cout << best << '\n';
  cout << (R + 1) << '\n';
}
