#include <bits/stdc++.h>
using namespace std;
long long int ans1[600005];
long long int ans2[600005];
int minsufa[600005];
int maxprefb[600005];
int res[600005];
int main() {
  int(n), (w);
  scanf("%d%d", &(n), &(w));
  ;
  vector<pair<int, int> > v1;
  vector<pair<pair<int, int>, int> > v2;
  for (int i = (0); i < (n); ++i) {
    int(a), (b);
    scanf("%d%d", &(a), &(b));
    ;
    if (b - a >= a) {
      v1.push_back(make_pair(a, -i - 1));
      v1.push_back(make_pair(b - a, i + 1));
    } else {
      v2.push_back(make_pair(make_pair(b, b - a), i));
    }
  }
  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());
  if (v2.size()) {
    maxprefb[0] = v2[0].first.second;
    for (int i = (1); i < (v2.size()); ++i) {
      maxprefb[i] = max(maxprefb[i - 1], v2[i].first.second);
    }
    minsufa[v2.size()] = 1e9;
    minsufa[v2.size() - 1] =
        v2[v2.size() - 1].first.first - v2[v2.size() - 1].first.second;
    for (int i = (v2.size() - 2); i >= (0); --i) {
      minsufa[i] = min(minsufa[i + 1], v2[i].first.first - v2[i].first.second);
    }
  }
  ans1[0] = 0;
  for (int i = (1); i < (v1.size() + 1); ++i) {
    ans1[i] = ans1[i - 1] + v1[i - 1].first;
  }
  ans2[0] = 0;
  int j = 0;
  long long int pref = 0;
  while (j < v2.size()) {
    pref += v2[j].first.first;
    ans2[2 * j + 1] =
        min(pref - maxprefb[j], pref + minsufa[j + 1] - v2[j].first.first);
    ans2[2 * j + 2] = pref;
    j++;
  }
  long long int best = 1e9 * 1LL * 1e9;
  int dlak = -1;
  for (int k = (0); k < (w + 1); ++k) {
    int l = w - k;
    if (k <= v1.size() && l <= 2 * v2.size()) {
      if (ans1[k] + ans2[l] < best) {
        best = ans1[k] + ans2[l];
        dlak = k;
      }
    }
  }
  cout << best << endl;
  for (int i = (0); i < (n); ++i) res[i] = 0;
  for (int i = (0); i < (dlak); ++i) {
    if (v1[i].second < 0)
      res[-v1[i].second - 1] = 1;
    else
      res[v1[i].second - 1] = 2;
  }
  int l = w - dlak;
  if (l % 2 == 0) {
    for (int j = (0); j < (l / 2); ++j) res[v2[j].second] = 2;
  } else {
    if (ans2[l + 1] - ans2[l] == maxprefb[l / 2]) {
      bool ok = false;
      for (int j = (0); j < (l / 2 + 1); ++j) {
        if (!ok && v2[j].first.second == maxprefb[l / 2])
          res[v2[j].second] = 1, ok = true;
        else
          res[v2[j].second] = 2;
      }
    } else {
      for (int j = (0); j < (l / 2); ++j) {
        res[v2[j].second] = 2;
      }
      for (int j = (l / 2); j < (v2.size()); ++j) {
        if (v2[j].first.first - v2[j].first.second == minsufa[l / 2 + 1]) {
          res[v2[j].second] = 1;
          break;
        }
      }
    }
  }
  for (int i = (0); i < (n); ++i) printf("%d", res[i]);
  printf("\n");
  return 0;
}
