#include <bits/stdc++.h>
using namespace std;
const int MAX = 600000;
int tree_cnt[MAX + 5];
long long tree_cost[MAX + 5];
void update_cnt(int i, int val) {
  while (i <= MAX) {
    tree_cnt[i] += val;
    i += (i & -i);
  }
}
int find_cnt(int i) {
  int res = 0;
  while (i) {
    res += tree_cnt[i];
    i -= (i & -i);
  }
  return res;
}
void update_cost(int i, int val) {
  while (i <= MAX) {
    tree_cost[i] += val;
    i += (i & -i);
  }
}
long long find_cost(int i) {
  long long res = 0;
  while (i) {
    res += tree_cost[i];
    i -= (i & -i);
  }
  return res;
}
struct data {
  int a, b, idx;
  data() {}
  data(int _a, int _b, int _idx) : a(_a), b(_b), idx(_idx) {}
  void read(int _idx) { scanf("%d%d", &a, &b), idx = _idx; }
  bool operator<(const data &rhs) const { return b < rhs.b; }
} D[300005];
bool cmp(const data &a, const data &b) { return a.a < b.a; }
vector<int> cost;
int ans[300005];
int n, w;
int getIdx(int a) {
  return lower_bound(cost.begin(), cost.end(), a) - cost.begin() + 1;
}
int main() {
  scanf("%d%d", &n, &w);
  for (int i = 0; i < n; ++i) {
    D[i].read(i);
    cost.push_back(D[i].a), cost.push_back(D[i].b - D[i].a);
  }
  sort(cost.begin(), cost.end());
  cost.erase(unique(cost.begin(), cost.end()), cost.end());
  for (int i = 0; i < n; ++i) {
    update_cnt(getIdx(D[i].a), 1);
    update_cost(getIdx(D[i].a), D[i].a);
  }
  long long sum = 1ll << 60;
  int idx = -1, f_piv = -1;
  if (w <= n) {
    sort(D, D + n, cmp), sum = 0;
    for (int i = 0; i < w; ++i) sum += D[i].a, ans[D[i].idx] = 1;
  }
  sort(D, D + n);
  long long add_a = 0;
  for (int i = 0; i < n; ++i) {
    update_cnt(getIdx(D[i].a), -1);
    update_cost(getIdx(D[i].a), -D[i].a);
    int rest_cnt = w - 2 - i;
    int s = 1, e = cost.size() + 1, piv = -1;
    while (s <= e) {
      int mid = (s + e) >> 1;
      if (find_cnt(mid) >= rest_cnt)
        piv = mid, e = mid - 1;
      else
        s = mid + 1;
    }
    if (piv != -1) {
      int piv_cnt = find_cnt(piv);
      long long tmp_sum = add_a + find_cost(piv) -
                          (piv_cnt - rest_cnt) * cost[piv - 1] + D[i].b;
      if (sum > tmp_sum) {
        sum = tmp_sum, idx = i, f_piv = piv;
      }
    }
    add_a += D[i].a;
    update_cnt(getIdx(D[i].b - D[i].a), 1);
    update_cost(getIdx(D[i].b - D[i].a), D[i].b - D[i].a);
  }
  printf("%I64d\n", sum);
  if (idx != -1) {
    memset(ans, 0, sizeof(ans));
    ans[D[idx].idx] = 2, w -= 2;
    vector<data> v;
    for (int i = 0; i < idx; ++i)
      ans[D[i].idx] = 1, w--, v.push_back(data(0, D[i].b - D[i].a, D[i].idx));
    for (int i = idx + 1; i < n; ++i) v.push_back(data(0, D[i].a, D[i].idx));
    sort(v.begin(), v.end());
    for (int i = 0; i < w; ++i) ans[v[i].idx]++;
  }
  for (int i = 0; i < n; ++i) printf("%d", ans[i]);
}
