#include <bits/stdc++.h>
using namespace std;
int z, n, a, b, w;
set<pair<int, int> > took, avail;
pair<pair<int, int>, int> level[300007];
int res[300007];
int bestres[300007];
long long ret, bestv;
int cur, bestid;
void puttwo(int i) {
  avail.insert(make_pair(level[i].first.second - level[i].first.first, n + i));
}
void take(pair<int, int> p, bool next = true, bool put = true) {
  int i = (p.second >= n ? p.second - n : p.second);
  int id = level[i].second;
  assert(avail.erase(p) == 1);
  if (put) took.insert(p);
  cur++;
  ret += p.first;
  res[id]++;
  if (res[id] == 1) {
    if (next) puttwo(i);
  } else {
    took.erase(make_pair(level[i].first.first, i));
  }
}
void take(bool next = true) {
  while (cur < w) {
    pair<int, int> p = *avail.begin();
    take(p, next);
  }
}
void giveback(pair<int, int> p) {
  int i = (p.second >= n ? p.second - n : p.second);
  int id = level[i].second;
  took.erase(p);
  avail.insert(p);
  res[id]--;
  if (res[id] == 0) {
    avail.erase(make_pair(level[i].first.second - level[i].first.first, n + i));
  }
  cur--;
  ret -= p.first;
}
void giveback() {
  while (cur > w) {
    pair<int, int> p = *took.rbegin();
    giveback(p);
  }
}
struct mysort {
  bool operator()(const pair<pair<int, int>, int>& a,
                  const pair<pair<int, int>, int>& b) const {
    return a.first.second < b.first.second;
  }
};
int solve(int bv, bool first = true) {
  avail.clear();
  took.clear();
  memset(res, 0, sizeof res);
  cur = ret = 0;
  for (int i = 0; i < n; i++) {
    avail.insert(make_pair(level[i].first.first, i));
  }
  for (int i = 0; i < w - n; i++) {
    take(make_pair(level[i].first.first, i), true, false);
  }
  take(false);
  bestv = ret;
  bestid = (w - n + 1) / 2 - 1;
  for (int i = 0; i < n; i++) bestres[i] = res[i];
  for (int i = max(0, w - n); i < min(n, w); i++) {
    if (took.count(make_pair(level[i].first.first, i))) {
      puttwo(i);
      assert(took.erase(make_pair(level[i].first.first, i)) == 1);
    } else {
      take(make_pair(level[i].first.first, i), true, false);
    }
    giveback();
    while (avail.size() && took.size() &&
           took.rbegin()->first > avail.begin()->first) {
      take(*avail.begin());
      giveback(*took.rbegin());
    }
    if (first && bestv > ret) {
      bestv = ret;
      bestid = i;
    }
    if (!first && bv == i) {
      for (int i = 0; i < n; i++) bestres[i] = res[i];
      return ret;
    }
  }
  return bestid;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> w;
  for (int i = 0; i < n; i++) {
    cin >> level[i].first.first >> level[i].first.second;
    level[i].second = i;
  }
  sort(level, level + n, mysort());
  solve(0, true);
  cout << bestv << endl;
  bestv = solve(bestid, false);
  for (int i = 0; i < n; i++) cout << bestres[i];
  cout << endl;
  return 0;
}
