#include <bits/stdc++.h>
using namespace std;
const int INF30 = 1 << 30;
const long long INF60 = (1LL) << 60;
const int MAXN = 300000;
const int MAXV = 600001;
int N, W, cprTimes[2 * MAXN], freqBIT[MAXV], res[MAXN];
long long valBIT[MAXV];
pair<int, int> ordTimes[MAXV];
struct level {
  int a, b, idx;
  level() {}
  bool operator<(const level &rhs) const {
    if (b == rhs.b) {
      return a < rhs.a;
    } else {
      return b < rhs.b;
    }
  }
} box[MAXN];
void addBIT(int idx, long long add, int sign) {
  ++idx;
  while (idx < MAXV) {
    freqBIT[idx] += sign;
    valBIT[idx] += add * sign;
    idx += (idx & -idx);
  }
}
int sfreqBIT(int idx) {
  ++idx;
  int res = 0;
  while (idx > 0) {
    res += freqBIT[idx];
    idx -= (idx & -idx);
  }
  return res;
}
long long svalBIT(int idx) {
  ++idx;
  long long res = 0;
  while (idx > 0) {
    res += valBIT[idx];
    idx -= (idx & -idx);
  }
  return res;
}
long long smallsum(int c) {
  if (c == 0) {
    return 0;
  }
  int low = 0, high = 2 * N;
  while (low < high) {
    int mid = (low + high) / 2;
    if (sfreqBIT(mid) < c) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  if (low == 2 * N) {
    return INF60;
  } else {
    return svalBIT(low);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin >> N >> W;
  for (int i = 0; i < N; i++) {
    cin >> box[i].a >> box[i].b;
    box[i].idx = i;
  }
  sort(box, box + N);
  for (int i = 0; i < N; i++) {
    ordTimes[2 * i] = pair<int, int>(box[i].a, 2 * i);
    ordTimes[2 * i + 1] = pair<int, int>(box[i].b - box[i].a, 2 * i + 1);
  }
  sort(ordTimes, ordTimes + 2 * N);
  for (int i = 0; i < 2 * N; i++) {
    cprTimes[ordTimes[i].second] = i;
  }
  for (int i = 0; i < N; i++) {
    addBIT(cprTimes[2 * i], box[i].a, 1);
  }
  long long psum = 0, mnTime = smallsum(W);
  int bestIdx = -1;
  for (int i = 0; i < N; i++) {
    int nLeft = W - i - 2;
    if (nLeft < 0) {
      break;
    }
    addBIT(cprTimes[2 * i], box[i].a, -1);
    long long curTime = psum + box[i].b + smallsum(nLeft);
    if (curTime < mnTime) {
      mnTime = curTime;
      bestIdx = i;
    }
    psum += box[i].a;
    addBIT(cprTimes[2 * i + 1], box[i].b - box[i].a, 1);
  }
  if (bestIdx == -1) {
    for (int i = 0; i < N; i++) {
      ordTimes[2 * i] = pair<int, int>(box[i].a, 2 * i);
      ordTimes[2 * i + 1] = pair<int, int>(INF30, 2 * i + 1);
    }
    sort(ordTimes, ordTimes + 2 * N);
    for (int i = 0; i < W; i++) {
      res[box[ordTimes[i].second / 2].idx] = 1;
    }
  } else {
    for (int i = 0; i < bestIdx; i++) {
      res[box[i].idx] = 1;
    }
    res[box[bestIdx].idx] = 2;
    for (int i = 0; i < N; i++) {
      if (i < bestIdx) {
        ordTimes[2 * i] = pair<int, int>(INF30, 2 * i);
        ordTimes[2 * i + 1] = pair<int, int>(box[i].b - box[i].a, 2 * i + 1);
      } else if (i == bestIdx) {
        ordTimes[2 * i] = pair<int, int>(INF30, 2 * i);
        ordTimes[2 * i + 1] = pair<int, int>(INF30, 2 * i + 1);
      } else {
        ordTimes[2 * i] = pair<int, int>(box[i].a, 2 * i);
        ordTimes[2 * i + 1] = pair<int, int>(INF30, 2 * i + 1);
      }
    }
    sort(ordTimes, ordTimes + 2 * N);
    for (int i = 0; i < W - bestIdx - 2; i++) {
      if (ordTimes[i].second % 2 == 0) {
        res[box[ordTimes[i].second / 2].idx] = 1;
      } else {
        res[box[ordTimes[i].second / 2].idx] = 2;
      }
    }
  }
  cout << mnTime << '\n';
  for (int i = 0; i < N; i++) {
    cout << res[i];
  }
  cout << '\n';
  return 0;
}
