#include <bits/stdc++.h>
#pragma comment(linker, "/stack:32000000")
using namespace std;
const int INF = 2147483647;
const long long LLINF = 9223372036854775807LL;
const int cinf = 1e9 + 10;
struct tt {
  multiset<int> m1;
  multiset<int> m2;
  long long cursum;
  tt() : cursum(0) {}
  void add(int x) {
    m1.insert(x);
    cursum += x;
  }
  void del(int x) {
    if (m1.find(x) != m1.end())
      m1.erase(m1.find(x)), cursum -= x;
    else if (m2.find(x) != m2.end())
      m2.erase(m2.find(x));
  }
  long long sum(int cnt) {
    if (int((m1).size()) + int((m2).size()) < cnt) return 1e18;
    while (int((m1).size()) < cnt) {
      cursum += *m2.begin();
      m1.insert(*m2.begin());
      m2.erase(m2.begin());
    }
    while (int((m1).size()) > cnt) {
      cursum -= *m1.rbegin();
      m2.insert(*m1.rbegin());
      m1.erase(m1.find(*m1.rbegin()));
    }
    return cursum;
  }
};
int main() {
  int n, w;
  scanf("%d%d", &n, &w);
  vector<pair<pair<int, int>, int> > v(n);
  for (int i = 0; i < n; ++i)
    scanf("%d%d", &v[i].first.first, &v[i].first.second), v[i].second = i;
  sort(v.begin(), v.end());
  long long bestans = 1e18;
  for (int iter = 0; iter < 2; ++iter) {
    vector<int> ans(n);
    tt t;
    for (int i = 0; i < n; ++i) t.add(v[i].first.second);
    set<pair<pair<int, int>, int> > st(v.begin(), v.end());
    int cc = 0;
    long long curcost = 0;
    while (!st.empty()) {
      pair<pair<int, int>, int> cur = *st.begin();
      st.erase(st.begin());
      if (cur.first.second < cinf) t.del(cur.first.second);
      int rem = w - cc;
      if (rem >= 0 && rem % 2 == 0) {
        long long tcost = t.sum(rem / 2);
        if (iter == 1 && curcost + tcost == bestans) {
          cout << curcost + tcost << "\n";
          vector<pair<pair<int, int>, int> > tmp(st.begin(), st.end());
          vector<pair<int, int> > tm;
          for (int i = 0; i < int((tmp).size()); ++i) {
            if (tmp[i].first.second < cinf)
              tm.push_back(make_pair(tmp[i].first.second, tmp[i].second));
          }
          sort(tm.begin(), tm.end());
          for (int i = 0; i < rem / 2; ++i) ans[tm[i].second] = 2;
          for (int i = 0; i < n; ++i) printf("%d", ans[i]);
          printf("\n");
          return 0;
        }
        if (curcost + tcost < bestans) {
          bestans = curcost + tcost;
        }
      }
      ++cc;
      ans[cur.second]++;
      curcost += cur.first.first;
      if (cur.first.second < cinf)
        st.insert(make_pair(make_pair(cur.first.second - cur.first.first, cinf),
                            cur.second));
    }
    if (curcost < bestans) {
      bestans = curcost;
      cout << curcost << "\n";
      for (int i = 0; i < n; ++i) printf("%d", ans[i]);
      printf("\n");
      return 0;
    }
  }
  return 0;
}
