호랑이

바이트랜드의 호랑이는 특이한 동물로, 그 독특한 습성은 오래전부터 동물학자와 수학자를 매료시켜 왔다. 최근 이들이 여러 종으로 나뉜다는 사실이 밝혀졌다. 어떤 호랑이가 자기보다 $k$배 이상 작은 호랑이를 만나면 공격해서 잡아먹지만 자기보다 큰 호랑이는 절대 건드리지 않을 때, 이 호랑이를 $k$-호랑이라고 부른다. 즉, 크기가 $r$인 $k$-호랑이는 $r \ge k \cdot s$일 때에만 크기가 $s$인 호랑이를 잡아먹는다.

바이트랜드 동물원에는 호랑이 $n$마리가 산다. 공간이 부족하기 때문에 원장은 어떤 호랑이도 잡아먹히지 않도록 하면서 되도록 적은 수의 우리에 동물들을 배치하려고 한다. 두 호랑이는 서로를 잡아먹지 않을 때에만 같은 우리에 둘 수 있다. 필요한 우리의 최소 개수를 구하라.

표준 입력의 첫째 줄에는 동물원에 있는 호랑이의 수를 나타내는 정수 $n$ ($1 \le n \le 500\,000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 호랑이 하나를 설명하는 두 정수 $r_i$와 $k_i$ ($1 \le r_i \le 1\,000\,000\,000$, $2 \le k_i \le 1\,000\,000$)가 공백 하나로 구분되어 주어진다. 이는 $i$번째 호랑이가 크기 $r_i$인 $k_i$-호랑이임을 뜻한다.

모든 호랑이를 안전하게 배치할 수 있는 우리의 최소 개수를 정수 하나로 표준 출력에 출력하라.

예제 설명. 위 예제에서 크기가 $28$, $18$, $15$인 호랑이는 $1$번 우리에서 함께 지낼 수 있고, 크기가 $10$, $8$인 호랑이는 $2$번 우리에 둘 수 있으므로 우리 두 개면 충분하다.