막대에 꿰인 베이글

비텍은 장터에 가서 가장 맛있는 베이글을 파는 가판대를 금세 찾아냈다. 오래 고민하지 않고 한 묶음을 샀다. 이 나라에서 베이글은 대부분의 장터처럼 고리에 끼우는 것이 아니라, 곧게 뻗은 막대에 꿰어서 판다. 베이글은 막대의 왼쪽 끝이나 오른쪽 끝에서만 하나씩 빼낼 수 있다.

각 베이글은 두 개의 값을 가진다. 바깥지름 $z$와 안지름(가운데 구멍의 지름) $w$이며, 항상 $1 \le w < z$이다.

비텍이 다른 베이글들 사이에 낀 베이글 하나를 빼내려 한다고 하자. 이때 한 베이글을 다른 베이글에 통과시켜 볼 수 있다. 두 베이글 중 어느 한쪽의 안지름이 다른 쪽의 바깥지름보다 크거나 같을 때에만, 즉 한 베이글의 구멍이 다른 베이글이 지나갈 만큼 충분히 클 때에만 통과가 가능하다. 두 구멍 모두 충분히 크지 않으면 통과할 수 없으므로, 두 베이글 중 하나를 먼저 왼쪽이나 오른쪽 끝에서 빼내야 한다.

비텍은 베이글 하나를 골랐다. 고른 베이글을 막대의 한쪽 끝으로 빼내려면, 그 끝과 고른 베이글 사이에 남아 있는 모든 베이글을 통과해야 한다. 통과할 수 없는 베이글은 먼저 그 끝에서 빼내야 한다(한 끝에서 베이글을 빼내면 그 쪽으로 더 바깥에 있는 베이글도 모두 함께 빠진다). 고른 베이글을 빼낼 수 있게 되기까지 최소 몇 개의 다른 베이글을 빼내야 하는지 구하여라.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \le m \le n \le 1{,}000{,}000$). 각각 막대에 꿰인 베이글의 개수와, 비텍이 고른 베이글이 왼쪽에서 몇 번째인지를 나타낸다.

이어지는 $n$개의 줄에는 왼쪽부터 순서대로 각 베이글의 정보가 주어진다. 그중 $i$번째 줄에는 두 정수 $w_i$와 $z_i$가 공백 하나로 구분되어 주어지며 ($1 \le w_i < z_i \le 10^9$), 각각 $i$번째 베이글의 안지름과 바깥지름을 나타낸다.

고른 베이글을 빼내기 위해 추가로 빼내야 하는 베이글의 최소 개수를 정수 하나로 출력한다. 비텍이 고른 베이글 자신은 세지 않는다.