#include <bits/stdc++.h>
using namespace std;
const long long inf = 2e18 + 7;
const long long mod = 1e9 + 7;
const double eps = 1e-9;
const double PI = 2 * acos(0.0);
const double E = 2.71828;
int n, w;
int a[300005], b[300005];
set<pair<int, int> > x, y;
int out[300005];
long long res = 0;
void addOne() {
  int val = (*x.begin()).first, pos = (*x.begin()).second;
  x.erase(x.begin());
  y.erase(make_pair(b[pos], pos));
  res += val;
  if (!out[pos]) {
    x.insert(make_pair(b[pos] - a[pos], pos));
  }
  ++out[pos];
  --w;
}
void addTwo() {
  int val = (*y.begin()).first, pos = (*y.begin()).second;
  y.erase(y.begin());
  x.erase(make_pair(a[pos], pos));
  res += val;
  out[pos] = 2;
  w -= 2;
}
int main(void) {
  scanf("%d %d", &n, &w);
  for (int(i) = 0; (i) < (n); ++(i)) {
    scanf("%d %d", a + i, b + i);
    x.insert(make_pair(a[i], i));
    y.insert(make_pair(b[i], i));
  }
  while (w) {
    if (w % 2 || x.size() == 1 || y.empty()) {
      addOne();
    } else {
      int valTwo = (*y.begin()).first;
      int val1 = (*x.begin()).first;
      int val2 = (*(++x.begin())).first;
      if (val1 + val2 < valTwo) {
        addOne();
        addOne();
      } else {
        addTwo();
      }
    }
  }
  cout << res << "\n";
  for (int(i) = 0; (i) < (n); ++(i)) printf("%d", out[i]);
  printf("\n");
  return 0;
}
