Bagels on a Stick

Witek went to a fair and quickly spotted the stall selling the best bagels. Without much thought he bought a portion of them. In Byteland, bagels are always threaded onto a straight stick, not onto a ring like at most fairs. Bagels can be taken off only from the left end or the right end of the stick, one at a time.

Each bagel has two values: an outer diameter $z$ and an inner diameter (the hole) $w$, with $1 \le w < z$.

Suppose Witek wants to free a bagel that sits between others. He may try to slide one bagel through another. This works only when the inner diameter of one of the two bagels is at least the outer diameter of the other, that is, when one bagel's hole is wide enough for the other to pass through it. If neither hole is wide enough, the bagels cannot pass, so one of the two must first be taken off from the left or right end.

Witek has chosen one particular bagel. To free it, he slides it off one end of the stick, and it must pass through every bagel that still lies between it and that end. Any bagel it cannot pass through must be removed from that end first (removing a bagel from an end also removes every bagel farther out on that side). Determine the minimum number of other bagels Witek must take off before he can free his chosen one.

The first line contains two integers $n$ and $m$ ($1 \le m \le n \le 1{,}000{,}000$): the number of bagels on the stick and the position, counted from the left, of the bagel Witek chose.

Each of the next $n$ lines describes one bagel, in order from left to right. The $i$-th of these lines contains two integers $w_i$ and $z_i$ ($1 \le w_i < z_i \le 10^9$), separated by a single space, the inner and outer diameter of the $i$-th bagel.

Print a single integer: the minimum number of other bagels Witek must take off in order to free his chosen bagel. Do not count the chosen bagel itself.