#include <bits/stdc++.h>
using namespace std;
long n, nw;
long a[300005], b[300005], minv[300005], maxv[300005], ans[300005];
long long sumone[300005 << 1], sumtwo[300005 << 1];
vector<pair<long, long> > one, two;
void input() {
  long i, conlai;
  scanf("%ld %ld", &n, &nw);
  for ((i) = 0; (i) < (n); (i)++) {
    scanf("%ld %ld", &a[i], &b[i]);
    b[i] -= a[i];
    if (a[i] <= b[i]) {
      one.push_back(make_pair(a[i], i));
      one.push_back(make_pair(b[i], i));
    } else
      two.push_back(make_pair(a[i] + b[i], i));
  }
  sort(one.begin(), one.end());
  sort(two.begin(), two.end());
  long sz1 = one.size();
  long sz2 = two.size();
  minv[sz2] = 2147483647;
  maxv[0] = 0;
  for ((i) = (sz2 - 1); (i) >= 0; (i)--)
    minv[i] = ((minv[i + 1]) < (a[two[i].second]) ? (minv[i + 1])
                                                  : (a[two[i].second]));
  for ((i) = 0; (i) < (sz2); (i)++)
    maxv[i + 1] =
        ((maxv[i]) > (b[two[i].second]) ? (maxv[i]) : (b[two[i].second]));
  sumone[0] = sumtwo[0] = 0;
  for ((i) = 0; (i) < (sz1); (i)++) sumone[i + 1] = sumone[i] + one[i].first;
  for ((i) = 0; (i) < (sz2); (i)++) sumtwo[i + 1] = sumtwo[i] + two[i].first;
  long long kq = 9223372036854775807LL, temp;
  long sone, type = 0;
  for ((i) = (0); (i) <= (sz1); (i)++) {
    temp = sumone[i];
    conlai = nw - i;
    if (i <= nw && conlai <= sz2 * 2) {
      if (conlai & 1) {
        temp += sumtwo[conlai >> 1] + minv[conlai >> 1];
        type = 0;
        if (sumone[i] + sumtwo[conlai >> 1] + two[conlai >> 1].first -
                maxv[conlai >> 1] <
            temp) {
          temp = sumone[i] + sumtwo[conlai >> 1] + two[conlai >> 1].first -
                 maxv[conlai >> 1];
          type = 1;
        }
      } else
        temp += sumtwo[conlai >> 1];
      if (temp < kq) {
        kq = temp;
        sone = i;
      }
    }
  }
  for ((i) = 0; (i) < (sone); (i)++) ans[one[i].second]++;
  for ((i) = 0; (i) < ((nw - sone) >> 1); (i)++) ans[two[i].second] = 2;
  if ((nw - sone) & 1) {
    long vt;
    if (type == 0) {
      temp = 2147483647;
      for ((i) = ((nw - sone) >> 1); (i) <= (sz2 - 1); (i)++)
        if (a[two[i].second] < temp)
          temp = a[two[i].second], vt = two[i].second;
    } else {
      temp = -1;
      for ((i) = 0; (i) < ((nw - sone) >> 1); (i)++)
        if (b[two[i].second] > temp)
          temp = b[two[i].second], vt = two[i].second;
      ans[two[(nw - sone) >> 1].second] = 2;
    }
    ans[vt] = 1;
  }
  printf("%I64d\n", kq);
  for ((i) = 0; (i) < (n); (i)++) printf("%ld", ans[i]);
  printf("\n");
}
int main() {
  input();
  return 0;
}
