#include <bits/stdc++.h>
using namespace std;
multiset<pair<int, int> > S;
multiset<pair<int, int> >::iterator it;
int star[310000], i, n, m, id;
long long ans, tmp;
struct ppp {
  int x, y, id;
  friend bool operator<(const ppp& a, const ppp& b) { return a.y < b.y; }
} a[310000];
int main() {
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; ++i) scanf("%d%d", &a[i].x, &a[i].y), a[i].id = i;
  sort(a + 1, a + n + 1);
  for (i = 1; i <= n; ++i) S.insert(make_pair(a[i].x, i)), tmp += a[i].x;
  ans = 1ll << 60;
  for (i = 0; i <= n; ++i) {
    if (i != 0) {
      tmp += a[i].y - a[i].x;
      if (S.count(make_pair(a[i].x, i)))
        S.erase(make_pair(a[i].x, i));
      else
        tmp += a[i].x;
      S.insert(make_pair(a[i].y - a[i].x, i));
    }
    if (i > m) break;
    while (i + S.size() > m) {
      it = S.end();
      it--;
      tmp -= it->first;
      S.erase(it);
    }
    if (i + S.size() == m && tmp < ans) ans = tmp, id = i;
  }
  printf("%I64d\n", ans);
  S.clear();
  for (i = 1; i <= id; ++i)
    star[a[i].id]++, S.insert(make_pair(a[i].y - a[i].x, a[i].id));
  for (i = id + 1; i <= n; ++i) S.insert(make_pair(a[i].x, a[i].id));
  for (i = id + 1; i <= m; ++i) {
    it = S.begin();
    star[it->second]++;
    S.erase(it);
  }
  for (i = 1; i <= n; ++i) printf("%d", star[i]);
}
