#include <bits/stdc++.h>
using namespace std;
int A[1 << 20];
int B[1 << 20];
int C[1 << 20];
int main() {
  int n, w;
  scanf("%d%d", &n, &w);
  int i;
  vector<pair<int, int> > v;
  for (i = (0); i < (n); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    b -= a;
    A[i] = a + a;
    B[i] = b + b;
    if (b >= a) {
      v.push_back(pair<int, int>(a + a, i));
      v.push_back(pair<int, int>(b + b, i));
    } else
      v.push_back(pair<int, int>(a + b, n + i));
  }
  sort((v).begin(), (v).end());
  memset(C, 0, sizeof(C));
  int cnt = 0;
  long long sum = 0;
  int pos = 0;
  while (cnt < w) {
    if (v[pos].second < n) {
      ++cnt;
      sum += v[pos].first;
      ++C[v[pos].second];
    } else {
      cnt += 2;
      sum += 2 * v[pos].first;
      C[v[pos].second - n] += 2;
    }
    ++pos;
  }
  if (cnt > w) {
    int best = 0;
    int wh = -1;
    for (i = (0); i < (pos); ++i)
      if (v[i].second < n) {
        int a = v[i].first;
        if (best < a) {
          best = a;
          wh = i;
        }
      } else {
        int a = B[v[i].second - n];
        if (best < a) {
          best = a;
          wh = i;
        }
      }
    for (i = (pos); i < (int((v).size())); ++i)
      if (v[i].second < n) {
        int a = 2 * v[pos - 1].first - v[i].first;
        if (best < a) {
          best = a;
          wh = i;
        }
      } else {
        int a = 2 * v[pos - 1].first - A[v[i].second - n];
        if (best < a) {
          best = a;
          wh = i;
        }
      }
    --cnt;
    if (wh < pos) {
      if (v[wh].second < n) {
        sum -= v[wh].first;
        --C[v[wh].second];
      } else {
        sum -= B[v[wh].second - n];
        --C[v[wh].second - n];
      }
    } else {
      sum -= 2 * v[pos - 1].first;
      C[v[pos - 1].second - n] -= 2;
      if (v[wh].second < n) {
        sum += v[wh].first;
        ++C[v[wh].second];
      } else {
        sum += A[v[wh].second - n];
        ++C[v[wh].second - n];
      }
    }
  }
  printf("%lld\n", sum / 2);
  for (i = (0); i < (n); ++i) printf("%d", C[i]);
  printf("\n");
  return 0;
};
