#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
const long long inf = mod * mod;
const long long d2 = (mod + 1) / 2;
const double EPS = 1e-6;
const double PI = acos(-1.0);
int ABS(int a) { return max(a, -a); }
long long ABS(long long a) { return max(a, -a); }
int L[210000];
int R[210000];
vector<int> v[210000];
int p[210000];
int bit[210000];
int sum(int a, int b) {
  if (a) return sum(0, b) - sum(0, a - 1);
  int ret = 0;
  for (; b >= 0; b = (b & (b + 1)) - 1) ret += bit[b];
  return ret;
}
void add(int a, int b) {
  for (; a < 210000; a |= a + 1) bit[a] += b;
}
int use[210000];
int main() {
  int a, b;
  scanf("%d%d", &a, &b);
  for (int i = 0; i < a; i++) {
    scanf("%d%d", L + i, R + i);
    v[L[i]].push_back(i);
  }
  int ret = 0;
  set<pair<int, int> > S;
  for (int i = 0; i < a; i++) {
    if (L[i]) S.insert(make_pair(R[i], i));
  }
  int at = 1;
  int sz = 0;
  for (int i = 0; i < b; i++) {
    if (S.empty()) {
      break;
    }
    p[i] = (*(S.rbegin())).second;
    sz++;
    S.erase(make_pair(R[p[i]], p[i]));
    add(L[p[i]], 1);
    int to = at;
    for (int j = 0; j < 50; j++) {
      int id = rand() % (i + 1);
      if (to < L[p[id]] && sum(0, L[p[id]]) >= L[p[id]]) to = L[p[id]] + 1;
    }
    if (to < L[p[i]]) {
      if (sum(0, L[p[i]]) >= L[p[i]]) to = L[p[i]] + 1;
    }
    while (to <= b) {
      if (sum(0, to) >= to)
        to++;
      else
        break;
    }
    while (at < to) {
      for (int j = 0; j < v[at].size(); j++) {
        S.erase(make_pair(R[v[at][j]], v[at][j]));
      }
      at++;
    }
  }
  for (int i = 0; i < sz; i++) printf("%d ", p[i]);
  printf("\n");
  for (int i = 0; i < sz; i++) use[p[i]] = 1;
  set<int> S2;
  for (int i = sz + 1; i <= b; i++) {
    S2.insert(i);
  }
  int tmp = 0;
  for (int i = 0; i < a; i++) {
    if (!use[i]) {
      set<int>::iterator it = S2.lower_bound(R[i]);
      if (it != S2.end()) {
        tmp++;
        S2.erase(it);
      }
    }
  }
  for (int i = sz; i >= 0; i--) {
    ret = max(ret, i + tmp);
    S2.insert(i);
    if (i) {
      set<int>::iterator it = S2.lower_bound(R[p[i - 1]]);
      if (it != S2.end()) {
        tmp++;
        S2.erase(it);
      }
    }
  }
  printf("%d\n", a - ret);
}
