#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1, c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  return f == 1 ? x : -x;
}
const long long N = 6e5 + 4;
long long n, m, ans, a[N], vis[N], Ans[N];
priority_queue<pair<long long, long long> > one, two;
inline void upd(priority_queue<pair<long long, long long> > &q) {
  while (!q.empty() && vis[q.top().second]) q.pop();
}
signed main() {
  n = read();
  m = read();
  for (long long i = 1; i <= n; i++) {
    a[i] = read();
    a[i + n] = read() - a[i];
    one.push(make_pair(-a[i], i));
    two.push(make_pair(-a[i + n] - a[i], i));
  }
  for (; m--;) {
    upd(one);
    upd(two);
    pair<long long, long long> x = one.top(), y = two.top();
    one.pop();
    long long i;
    upd(one);
    if (m && !two.empty() && -x.first - one.top().first >= -y.first) {
      two.pop();
      one.push(x);
      i = y.second;
    } else
      i = x.second;
    if (i <= n) one.push(make_pair(-a[i + n], i + n));
    ans += a[i];
    Ans[i]++;
    vis[i] = 1;
  }
  cout << ans << "\n";
  for (long long i = 1; i <= n; i++) cout << Ans[i] + Ans[i + n];
  return (0 - 0);
}
