Problem: Everyone who has played Cut the Rope knows full well how the gameplay is organized. All levels in the game are divided into boxes. Initially only one box with some levels is available. Player should complete levels to earn stars, collecting stars opens new box with levels.

<image>

Imagine that you are playing Cut the Rope for the first time. Currently you have only the levels of the first box (by the way, it is called "Cardboard Box"). Each level is characterized by two integers: ai — how long it takes to complete the level for one star, bi — how long it takes to complete the level for two stars (ai < bi).

You want to open the next box as quickly as possible. So, you need to earn at least w stars. How do make it happen? Note that the level can be passed only once: either for one star or for two. You do not necessarily need to pass all the levels.

Input

The first line contains two integers n and w (1 ≤ n ≤ 3·105; 1 ≤ w ≤ 2n) — the number of levels in the first box and the number of stars you need to open another box. Each of the following n lines contains two integers ai and bi (1 ≤ ai < bi ≤ 109) — the attributes of the i-th level.

Output

In the first line print integer t — the minimum time you need to open the next box. 

In the next line, print n digits without spaces — the description of the optimal scenario: 

  * if you need to pass the i-th level for one star, the i-th digit should equal 1; 
  * if you need to pass the i-th level for two stars, the i-th digit should equal 2; 
  * if you do not need to pass the i-th level at all, the i-th digit should equal 0. 

Examples

Input

2 3
1 2
1 2


Output

3
12


Input

5 3
10 20
5 10
10 20
6 9
25 30


Output

14
01020

Note

In the first test sample, answer 21 is also assumed correct.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
inline void pisz(int n) { printf("%d\n", n); }
template <typename T, typename TT>
ostream &operator<<(ostream &s, pair<T, TT> t) {
  return s << "(" << t.first << "," << t.second << ")";
}
template <typename T>
ostream &operator<<(ostream &s, vector<T> t) {
  for (int(i) = 0; (i) < (((int)((t).size()))); ++(i)) s << t[i] << " ";
  return s;
}
pair<int, long long> operator+(const pair<int, long long> &a,
                               const pair<int, long long> &b) {
  return make_pair(a.first + b.first, a.second + b.second);
}
template <typename T, typename Aug>
struct AugTreap {
  struct Node {
    T v;
    int pr;
    Node *le, *ri;
    Aug al, ag;
  };
  Node *root;
  AugTreap() : root(0) {}
  inline static void recalc(Node *&n) {
    Aug left = n->le ? n->le->ag + n->al : n->al;
    n->ag = n->ri ? left + n->ri->ag : left;
  }
  inline void rotle(Node *&n) {
    Node *syn = n->le;
    n->le = syn->ri;
    syn->ri = n;
    n = syn;
    recalc(n->ri);
    recalc(n);
  }
  inline void rotri(Node *&n) {
    Node *syn = n->ri;
    n->ri = syn->le;
    syn->le = n;
    n = syn;
    recalc(n->le);
    recalc(n);
  }
  void insert_aux(Node *&n, const T &x, const Aug &aug) {
    if (!n) {
      n = new Node;
      n->v = x;
      n->pr = rand();
      n->le = n->ri = 0;
      n->al = n->ag = aug;
    } else if (x < n->v) {
      insert_aux(n->le, x, aug);
      if (n->pr > n->le->pr)
        rotle(n);
      else
        recalc(n);
    } else if (x > n->v) {
      insert_aux(n->ri, x, aug);
      if (n->pr > n->ri->pr)
        rotri(n);
      else
        recalc(n);
    } else {
      n->al = n->al + aug;
      recalc(n);
    }
  }
  void insert(const T &x, const Aug &aug) { insert_aux(root, x, aug); }
  Aug sumgeq_aux(const T &x, Node *n) {
    if (!n) return Aug();
    if (x > n->v) return sumgeq_aux(x, n->ri);
    if (x < n->v) {
      Aug left = sumgeq_aux(x, n->le) + n->al;
      return n->ri ? left + n->ri->ag : left;
    }
    return n->ri ? n->al + n->ri->ag : n->al;
  }
  Aug sumgeq(const T &x) { return sumgeq_aux(x, root); }
  Aug sumleq_aux(const T &x, Node *n) {
    if (!n) return Aug();
    if (x < n->v) return sumleq_aux(x, n->le);
    if (x > n->v) {
      Aug right = n->al + sumleq_aux(x, n->ri);
      return n->le ? n->le->ag + right : right;
    }
    return n->le ? n->le->ag + n->al : n->al;
  }
  Aug sumleq(const T &x) { return sumleq_aux(x, root); }
  Aug sumbetween_aux(const T &x, const T &y, Node *n) {
    if (!n) return Aug();
    if (y < n->v) return sumbetween_aux(x, y, n->le);
    if (x > n->v) return sumbetween_aux(x, y, n->ri);
    return sumgeq_aux(x, n->le) + n->al + sumleq_aux(y, n->ri);
  }
  Aug sumbetween(const T &x, const T &y) { return sumbetween_aux(x, y, root); }
  bool remove(const T &x) { return remove_aux(root, x); }
  bool remove_aux(Node *&n, const T &x) {
    if (!n) return 0;
    if (x < n->v) {
      bool wyn = remove_aux(n->le, x);
      if (wyn) recalc(n);
      return wyn;
    }
    if (x > n->v) {
      bool wyn = remove_aux(n->ri, x);
      if (wyn) recalc(n);
      return wyn;
    }
    remove_node(n);
    return 1;
  }
  void remove_node(Node *&n) {
    if (!n->le) {
      Node *syn = n->ri;
      delete n;
      n = syn;
    } else if (!n->ri) {
      Node *syn = n->le;
      delete n;
      n = syn;
    } else if (n->le->pr < n->ri->pr) {
      rotle(n);
      remove_node(n->ri);
      recalc(n);
    } else {
      rotri(n);
      remove_node(n->le);
      recalc(n);
    }
  }
  long long find_kth_sum(int k, Node *n) {
    if (k == 0) return 0;
    if (!n->le) {
      if (k <= n->al.first)
        return n->al.second / n->al.first * k;
      else
        return n->al.second + find_kth_sum(k - n->al.first, n->ri);
    } else {
      if (k <= n->le->ag.first)
        return find_kth_sum(k, n->le);
      else if (k <= n->le->ag.first + n->al.first)
        return n->le->ag.second +
               n->al.second / n->al.first * (k - n->le->ag.first);
      else
        return n->le->ag.second + n->al.second +
               find_kth_sum(k - n->le->ag.first - n->al.first, n->ri);
    }
  }
  long long find_kth_sum(int k) { return find_kth_sum(k, root); }
};
char ans[1000007];
int newindex[1000007];
int main() {
  int(n), (w);
  scanf("%d %d", &(n), &(w));
  vector<pair<pair<int, int>, int>> v;
  for (int(i) = 0; (i) < (n); ++(i)) {
    int(aa), (bb);
    scanf("%d %d", &(aa), &(bb));
    v.push_back(make_pair(make_pair(bb, aa), i));
  }
  sort(v.begin(), v.end());
  AugTreap<int, pair<int, long long>> tr;
  int niskich = 0;
  long long sumniskich = 0;
  for (auto it = v.begin(); it != v.end(); it++) {
    tr.insert(it->first.second, make_pair(1, it->first.second));
  }
  pair<long long, int> res(1001001001001001001LL, -1);
  if (w <= n) {
    (res) = min((res), (make_pair(tr.find_kth_sum(w), 0)));
    ;
  }
  for (auto it = v.begin(); it != v.end(); it++) {
    newindex[it->second] = niskich;
    niskich++;
    sumniskich += it->first.second;
    tr.insert(it->first.second, make_pair(-1, -it->first.second));
    tr.insert(it->first.first - it->first.second,
              make_pair(1, it->first.first - it->first.second));
    if (w <= n + niskich && w >= niskich)
      (res) =
          min((res),
              (make_pair(sumniskich + tr.find_kth_sum(w - niskich), niskich)));
    ;
  }
  printf("%lld\n", res.first);
  vector<pair<int, int>> opcje;
  for (int(i) = 0; (i) < (res.second); ++(i)) {
    ans[i] = '1';
    opcje.push_back(make_pair(v[i].first.first - v[i].first.second, i));
  }
  for (int(i) = (res.second); (i) <= (n - 1); ++i) {
    ans[i] = '0';
    opcje.push_back(make_pair(v[i].first.second, i));
  }
  sort(opcje.begin(), opcje.end());
  for (int(u) = 0; (u) < (w - res.second); ++(u)) {
    ans[opcje[u].second]++;
  }
  for (int(i) = 0; (i) < (n); ++(i)) printf("%c", ans[newindex[i]]);
}