#include <bits/stdc++.h>
const int N = 3e5;
const int INF = 2e9;
int n, w;
int A[N + 5], B[N + 5];
int Col[5 + 5], Ans[N + 5];
std::priority_queue<std::pair<int, int> > Q[5 + 5];
void Fizz();
void Push1(int);
void Push2(int);
void Push3(int);
void Push4(int);
void Push5(int);
int main() {
  scanf("%d%d", &n, &w), Col[1] = Col[5] = 1, Col[2] = 2;
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &A[i], &B[i]);
    Q[3].push(std::make_pair(-A[i], i)), Q[4].push(std::make_pair(-B[i], i));
  }
  long long tapAns = 0;
  for (int K = 1; K <= w; ++K) {
    Fizz();
    int tap[4 + 5] = {0, INF, INF, INF, INF};
    if (Q[3].size()) tap[1] = -Q[3].top().first;
    if (Q[5].size()) tap[2] = -Q[5].top().first;
    if (Q[4].size() && Q[1].size())
      tap[3] = -Q[4].top().first - Q[1].top().first;
    if (Q[4].size() && Q[2].size())
      tap[4] = -Q[4].top().first - Q[2].top().first;
    int Min = std::min(std::min(tap[1], tap[2]), std::min(tap[3], tap[4]));
    tapAns += 1ll * Min;
    if (Min == tap[1]) {
      int Zoe = Q[3].top().second;
      Push1(Zoe), Push5(Zoe), Q[3].pop();
    } else if (Min == tap[2]) {
      int Zoe = Q[5].top().second;
      Push2(Zoe), Q[5].pop();
    } else if (Min == tap[3]) {
      int Zoe = Q[4].top().second, Nico = Q[1].top().second;
      Push3(Nico), Push4(Nico), Push2(Zoe), Q[4].pop(), Q[1].pop();
    } else {
      int Zoe = Q[4].top().second, Nico = Q[2].top().second;
      Push1(Nico), Push5(Nico), Push2(Zoe), Q[4].pop(), Q[2].pop();
    }
  }
  printf("%lld\n", tapAns);
  for (int i = 1; i <= n; i++) printf("%d", Ans[i]);
  printf("\n");
  return 0;
}
void Fizz() {
  for (int i = 1; i <= 5; ++i)
    while (Q[i].size() && Ans[Q[i].top().second] != Col[i]) Q[i].pop();
}
void Push1(int p) { Ans[p] = Col[1], Q[1].push(std::make_pair(A[p], p)); }
void Push2(int p) {
  Ans[p] = Col[2], Q[2].push(std::make_pair(B[p] - A[p], p));
}
void Push3(int p) { Ans[p] = Col[3], Q[3].push(std::make_pair(-A[p], p)); }
void Push4(int p) { Ans[p] = Col[4], Q[4].push(std::make_pair(-B[p], p)); }
void Push5(int p) {
  Ans[p] = Col[5], Q[5].push(std::make_pair(-(B[p] - A[p]), p));
}
