#include <bits/stdc++.h>
using namespace std;
const int oo = 1000000009;
const double eps = 1e-6;
const int mod = 1000000007;
const int mx = 300005;
int f[mx], s[mx], n, w;
int play[mx];
int main() {
  scanf("%d%d", &n, &w);
  for (int i = 0; i < (n); ++i) scanf("%d %d", f + i, s + i);
  set<pair<int, pair<int, int> > > s1, s2;
  for (int i = 0; i < (n); ++i) {
    s1.insert(make_pair(f[i], make_pair(s[i] - f[i], i)));
    s2.insert(make_pair(s[i], make_pair(-1 * f[i], i)));
  }
  long long ans = 0;
  while (w > 0) {
    if ((w & 1) || (int)(s1.size()) == 1) {
      assert((int)(s1.size()) >= 1);
      pair<int, pair<int, int> > cur = *s1.begin();
      ans += cur.first;
      s1.erase(s1.begin());
      int i = cur.second.second;
      if (++play[i] == 1) {
        s2.erase(make_pair(s[i], make_pair(-1 * f[i], i)));
        s1.insert(make_pair(s[i] - f[i], make_pair(oo, i)));
      }
      --w;
      continue;
    }
    int from = 0;
    if ((int)(s1.size()) >= 2 && (int)(s2.size()) > 0) {
      pair<int, pair<int, int> > cur1 = *s1.begin();
      s1.erase(s1.begin());
      pair<int, pair<int, int> > cur2 = *s1.begin();
      s1.insert(cur1);
      pair<int, pair<int, int> > cur = *s2.begin();
      if (cur.first <= cur1.first + cur2.first) {
        from = 1;
      } else {
        from = 0;
      };
    } else if ((int)(s2.size()) == 0 && (int)(s1.size()) >= 2) {
      from = 0;
    } else {
      from = 1;
    }
    if (from == 0) {
      assert((int)(s1.size()) >= 2);
      pair<int, pair<int, int> > cur1 = *s1.begin();
      s1.erase(s1.begin());
      pair<int, pair<int, int> > cur2 = *s1.begin();
      s1.erase(s1.begin());
      ans += cur1.first;
      ans += cur2.first;
      int i = cur1.second.second;
      if (++play[i] == 1) {
        s2.erase(s2.find(make_pair(s[i], make_pair(-1 * f[i], i))));
        s1.insert(make_pair(s[i] - f[i], make_pair(oo, i)));
      }
      i = cur2.second.second;
      if (++play[i] == 1) {
        s2.erase(s2.find(make_pair(s[i], make_pair(-1 * f[i], i))));
        s1.insert(make_pair(s[i] - f[i], make_pair(oo, i)));
      }
    } else {
      assert((int)(s2.size()) >= 1);
      pair<int, pair<int, int> > cur = *s2.begin();
      ans += cur.first;
      int i = cur.second.second;
      play[i] = 2;
      s2.erase(s2.begin());
      s1.erase(s1.find(make_pair(f[i], make_pair(s[i] - f[i], i))));
    }
    w -= 2;
  }
  cout << ans << endl;
  for (int i = 0; i < (n); ++i) printf("%d", play[i]);
  printf("\n");
  return 0;
}
