#include <bits/stdc++.h>
using namespace std;
int n, w, used[300005];
long long ans, a[300005], b[300005];
priority_queue<pair<long long, int>, vector<pair<long long, int> >,
               greater<pair<long long, int> > >
    Q1, Q2;
priority_queue<pair<long long, int>, vector<pair<long long, int> >,
               less<pair<long long, int> > >
    Used;
int main() {
  scanf("%d %d", &n, &w);
  for (int i = 1; i <= n; i++) {
    scanf("%lld %lld", &a[i], &b[i]);
    Q1.push(make_pair(a[i], i));
    Q2.push(make_pair(b[i], i));
  }
  if (w == 1) {
    pair<long long, int> x = Q1.top();
    ans = x.first;
    used[x.second]++;
    printf("%lld\n", ans);
    for (int i = 1; i <= n; i++) printf("%d", used[i]);
    return 0;
  }
  while (w > 0 && !Q1.empty() && !Q2.empty()) {
    pair<long long, int> x = Q1.top();
    if (used[abs(x.second)] == 2) {
      Q1.pop();
      continue;
    }
    pair<long long, int> y = Q2.top();
    if (used[y.second]) {
      Q2.pop();
      continue;
    }
    if (x.first * 2 <= y.first) {
      int now = x.second;
      w--;
      ans += x.first;
      Q1.pop();
      if (now > 0) Q1.push(make_pair(b[now] - a[now], -now));
      used[abs(now)]++;
      Used.push(make_pair(x.first, abs(now)));
    } else {
      int now = y.second;
      w--, w--;
      ans += y.first;
      Q2.pop();
      used[now] = 2;
      Used.push(make_pair(b[now] - a[now], now));
    }
  }
  while (w > 0 && !Q1.empty()) {
    pair<long long, int> x = Q1.top();
    if (used[abs(x.second)] == 2) {
      Q1.pop();
      continue;
    }
    int now = x.second;
    w--;
    ans += x.first;
    Q1.pop();
    if (now > 0) Q1.push(make_pair(b[now] - a[now], -now));
    used[abs(now)]++;
    Used.push(make_pair(x.first, abs(now)));
  }
  while (w > 0 && !Q2.empty()) {
    pair<long long, int> y = Q2.top();
    if (used[y.second]) {
      Q2.pop();
      continue;
    }
    int now = y.second;
    w--, w--;
    ans += y.first;
    Q2.pop();
    used[now] = 2;
    Used.push(make_pair(b[now] - a[now], now));
  }
  if (w == -1) {
    pair<long long, int> x = Used.top();
    ans -= x.first;
    used[x.second]--;
  }
  int f = 1;
  while (f) {
    f = 0;
    while (!Q1.empty()) Q1.pop();
    while (!Used.empty()) Used.pop();
    for (int i = 1; i <= n; i++) {
      if (used[i] == 2)
        Used.push(make_pair(b[i], i));
      else if (used[i] == 1)
        Q1.push(make_pair(b[i] - a[i], i));
      else
        Q1.push(make_pair(a[i], i));
    }
    if (Q1.size() < 2 || Used.empty()) break;
    pair<long long, int> x = Q1.top();
    Q1.pop();
    pair<long long, int> y = Q1.top();
    Q1.pop();
    pair<long long, int> z = Used.top();
    Used.pop();
    if (x.first + y.first < z.first) {
      ans = ans - (z.first - x.first - y.first);
      used[x.second]++;
      used[y.second]++;
      used[z.second] = 0;
      f = 1;
    }
  }
  printf("%lld\n", ans);
  for (int i = 1; i <= n; i++) printf("%d", used[i]);
  return 0;
}
