#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
const int N = 6e5 + 10;
const long long mod = 1e9 + 7;
const long long mod2 = 998244353;
const long long inf = 4e18;
const int LOG = 22;
const int B = 560;
const int NB = N / B + 10;
struct PI {
  int first, second, id;
} A[N];
int n, w, ind, Ans[N];
long long tot = inf, arr[N], sum[NB], ps[N];
vector<int> vec[NB];
map<int, int> mp;
bool cmp(PI i, PI j) { return i.second < j.second; }
void build() {
  vector<int> Arr;
  Arr.push_back(0);
  for (int T = 0; T <= n / B; T++) {
    for (auto x : vec[T]) {
      Arr.push_back(x);
    }
    vec[T].clear();
    sum[T] = 0;
  }
  for (int i = 1; i <= n; i++) {
    vec[i / B].push_back(Arr[i]);
    sum[i / B] += Arr[i];
  }
}
void del(int x) {
  for (int T = 0; T <= n / B; T++) {
    if (!vec[T].empty() && vec[T].back() >= x) {
      sum[T] -= x;
      int i = 0;
      for (; i < (int)vec[T].size(); i++) {
        if (vec[T][i] == x) {
          break;
        }
      }
      vec[T].erase(vec[T].begin() + i);
      break;
    }
  }
}
void add(int x) {
  for (int T = 0; T <= n / B; T++) {
    if (vec[T].empty() || vec[T + 1].empty() || vec[T].back() >= x) {
      sum[T] += x;
      int i = 0;
      for (; i < (int)vec[T].size(); i++) {
        if (vec[T][i] >= x) {
          break;
        }
      }
      vec[T].insert(vec[T].begin() + i, x);
      break;
    }
  }
}
long long calc(int cnt) {
  cnt = max(cnt, 0);
  if (cnt > n) return inf;
  long long ret = 0;
  for (int T = 0; T <= n / B; T++) {
    if (cnt > (int)vec[T].size()) {
      ret += sum[T];
      cnt -= (int)vec[T].size();
    } else {
      for (int i = 0; i < (int)vec[T].size(); i++) {
        if (cnt) {
          cnt--;
          ret += vec[T][i];
        } else {
          break;
        }
      }
      break;
    }
  }
  if (cnt) return inf;
  return ret;
}
void show() {
  printf("checking vec : \n");
  for (int T = 0; T <= n / B; T++) {
    printf("T = %d\n", T);
    for (auto x : vec[T]) printf("%d ", x);
    printf("\n");
  }
}
int main() {
  scanf("%d%d", &n, &w);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &A[i].first, &A[i].second);
    A[i].id = i;
  }
  sort(A + 1, A + n + 1, cmp);
  for (int i = 1; i <= n; i++) {
    arr[i] = (i > w ? A[i].first : A[i].second - A[i].first);
    ps[i] = ps[i - 1] + A[i].first;
  }
  sort(arr + 1, arr + n + 1);
  for (int i = 1; i <= n; i++) {
    vec[i / B].push_back(arr[i]);
    sum[i / B] += arr[i];
  }
  for (int i = min(n, w); i >= 1; i--) {
    if (tot > ps[i] + calc(w - i)) {
      ind = i;
    }
    tot = min(tot, ps[i] + calc(w - i));
    del(A[i].second - A[i].first);
    add(A[i].first);
    if (i % (B - 3) == 0) {
      build();
    }
  }
  if (tot > calc(w)) {
    ind = 0;
  }
  tot = min(tot, calc(w));
  for (int i = 1; i <= n; i++) {
    arr[i] = (i > ind ? A[i].first : A[i].second - A[i].first);
  }
  sort(arr + 1, arr + n + 1);
  for (int i = 1; i <= w - ind; i++) {
    mp[arr[i]]++;
  }
  for (int i = 1; i <= n; i++) {
    arr[i] = (i > ind ? A[i].first : A[i].second - A[i].first);
    if (mp[arr[i]] > 0) {
      mp[arr[i]]--;
      Ans[A[i].id]++;
    }
  }
  for (int i = 1; i <= ind; i++) {
    Ans[A[i].id]++;
  }
  printf("%lld\n", tot);
  for (int i = 1; i <= n; i++) {
    printf("%d", Ans[i]);
  }
  return 0;
}
