#include <bits/stdc++.h>
using namespace std;
const int inf = INT_MAX;
struct entry {
  int cost;
  int index;
  entry(int cost_, int index_) {
    cost = cost_;
    index = index_;
  }
};
bool lessEntry(const entry& a, const entry& b) { return a.cost < b.cost; }
int main() {
  int n, w;
  int a, b;
  int delta[300000];
  char count[300000];
  vector<entry> singles;
  vector<entry> doubles;
  cin >> n >> w;
  for (int i = 0; i < n; i++) {
    cin >> a >> b;
    count[i] = '0';
    if (a <= b - a) {
      singles.push_back(entry(a, i));
      singles.push_back(entry(b - a, i));
    } else {
      doubles.push_back(entry(b, i));
      delta[i] = b - a;
    }
  }
  sort(singles.begin(), singles.end(), lessEntry);
  sort(doubles.begin(), doubles.end(), lessEntry);
  singles.push_back(entry(inf / 2, -1));
  doubles.push_back(entry(inf, -1));
  int i = 0;
  int j = 0;
  int curCost = 0;
  long long minTime = 0;
  while (curCost < w - 1) {
    if (2 * singles[i].cost < doubles[j].cost) {
      count[singles[i].index] += 1;
      minTime += singles[i].cost;
      curCost += 1;
      i++;
    } else {
      count[doubles[j].index] += 2;
      minTime += doubles[j].cost;
      curCost += 2;
      j++;
    }
  }
  if (curCost != w) {
    int costA = singles[i].cost;
    int costB = doubles[j].cost;
    int costC = doubles[j].cost;
    int costD = 0;
    if (i != 0) costB -= singles[i - 1].cost;
    int maxDeltaInd = -1;
    int maxDelta = 0;
    for (int k = 0; k <= j; k++) {
      if (maxDelta < delta[doubles[k].index]) {
        maxDeltaInd = k;
        maxDelta = delta[doubles[k].index];
      }
    }
    costC -= maxDelta;
    int minFirstInd = -1;
    int minFirst = inf;
    for (int k = j + 1; k < doubles.size() - 1; k++) {
      if (doubles[k].cost - delta[doubles[k].index] < minFirst) {
        minFirstInd = k;
        minFirst = doubles[k].cost - delta[doubles[k].index];
      }
    }
    costD += minFirst;
    int minCost = inf;
    minCost = min(minCost, costA);
    minCost = min(minCost, costB);
    minCost = min(minCost, costC);
    minCost = min(minCost, costD);
    if (minCost == costA) {
      count[singles[i].index] += 1;
    } else if (minCost == costB) {
      count[doubles[j].index] += 2;
      count[singles[i - 1].index] -= 1;
    } else if (minCost == costC) {
      count[doubles[j].index] += 2;
      count[doubles[maxDeltaInd].index] -= 1;
    } else if (minCost == costD) {
      count[doubles[minFirstInd].index] += 1;
    }
    minTime += minCost;
  }
  cout << minTime << endl;
  for (int i = 0; i < n; i++) {
    cout << count[i];
  }
  cout << endl;
  return 0;
}
