#include <bits/stdc++.h>
using namespace std;
template <typename T>
T mabs(const T &a) {
  return a < 0 ? -a : a;
}
set<pair<int, int> > avSum;
set<pair<int, int> > avA, usedA;
set<pair<int, int> > avB, usedB;
int A[300100], B[300100];
void addSum(int i) {
  avSum.erase(pair<int, int>(A[i] + B[i], i));
  avA.erase(pair<int, int>(A[i], i));
  usedB.insert(pair<int, int>(B[i], i));
}
void run() {
  int n, w;
  cin >> n >> w;
  for (int i = (0), ei = (n); i < ei; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    b -= a;
    A[i] = a;
    B[i] = b;
    avSum.insert(pair<int, int>(a + b, i));
    avA.insert(pair<int, int>(a, i));
  }
  long long res = 0;
  for (int i = (0), ei = (w); i < ei; i++) {
    set<pair<int, int> >::iterator sumIt = avSum.begin();
    set<pair<int, int> >::iterator aIt = avA.begin();
    set<pair<int, int> >::iterator bIt = avB.begin();
    set<pair<int, int> >::iterator it;
    long long newSum = 1e18;
    int move = -1;
    if (aIt != avA.end()) {
      long long here = res;
      here += aIt->first;
      if (here < newSum) {
        newSum = here;
        move = 0;
      }
    }
    if (bIt != avB.end()) {
      long long here = res;
      here += bIt->first;
      if (here < newSum) {
        newSum = here;
        move = 1;
      }
    }
    if (usedB.size() > 0 && sumIt != avSum.end()) {
      long long here = res;
      it = usedB.end();
      --it;
      here += sumIt->first - it->first;
      if (here < newSum) {
        newSum = here;
        move = 2;
      }
    }
    if (usedA.size() > 0 && sumIt != avSum.end()) {
      long long here = res;
      it = usedA.end();
      --it;
      here += sumIt->first - it->first;
      if (here < newSum) {
        newSum = here;
        move = 3;
      }
    }
    res = newSum;
    if (move == 0) {
      int ind = aIt->second;
      avA.erase(aIt);
      usedA.insert(pair<int, int>(A[ind], ind));
      avB.insert(pair<int, int>(B[ind], ind));
      avSum.erase(pair<int, int>(A[ind] + B[ind], ind));
    }
    if (move == 1) {
      int ind = bIt->second;
      avB.erase(bIt);
      usedB.insert(pair<int, int>(B[ind], ind));
      usedA.erase(pair<int, int>(A[ind], ind));
    }
    if (move == 2) {
      it = usedB.end();
      --it;
      int indb = it->second;
      avB.insert(pair<int, int>(B[indb], indb));
      usedB.erase(pair<int, int>(B[indb], indb));
      usedA.insert(pair<int, int>(A[indb], indb));
      addSum(sumIt->second);
    }
    if (move == 3) {
      it = usedA.end();
      --it;
      int inda = it->second;
      avA.insert(pair<int, int>(A[inda], inda));
      usedA.erase(pair<int, int>(A[inda], inda));
      avB.erase(pair<int, int>(B[inda], inda));
      avSum.insert(pair<int, int>(A[inda] + B[inda], inda));
      addSum(sumIt->second);
    }
  }
  char Res[300100] = {0};
  memset(Res, '0', n);
  for (auto p : usedA) Res[p.second] = '1';
  for (auto p : usedB) Res[p.second] = '2';
  cout << res << endl;
  puts(Res);
}
int main() {
  run();
  return 0;
}
