치타 무리 촬영

동물의 속도를 다루는 다큐멘터리 촬영팀이 전속력으로 달리는 치타를 한 화면에 여러 마리 담으려고 한다. 한 마리가 달리는 장면은 이미 여러 번 찍었으니, 이번에는 무리를 노린다.

치타를 상자 하나에 몰아넣었다가 한꺼번에 풀어놓는 방식은 위험해서 쓸 수 없다. 그래서 치타마다 출발 상자를 따로 두고 느린 치타를 먼저 풀어놓기로 했다. 시간이 지나면 빠른 치타가 느린 치타를 따라잡고, 어느 순간 무리가 가장 짧게 뭉친다. 촬영팀은 그 순간의 무리 길이를 알고 싶어 한다.

출발 상자는 모두 같은 지점에 있다고 본다. $k$번 치타는 시각 $t_k$에 풀려나고, 그 순간부터 일정한 속력 $v_k$로 달린다. 시각 $T$에서 무리의 길이는 가장 앞선 치타와 가장 뒤처진 치타 사이의 거리다.

길이는 모든 치타가 이미 출발한 시각, 즉 $T \ge \max(t_1, \dots, t_N)$에서만 잰다. 트랙은 충분히 길어서 무리가 가장 짧아지는 순간은 선두 치타가 결승선에 닿기 전에 온다. 무리 길이의 최솟값을 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 치타의 수 $N$ ($1 \le N \le 100000$)이 주어진다. 이어지는 $N$개의 줄에는 각각 두 정수 $t_k$와 $v_k$가 공백으로 구분되어 주어진다 ($1 \le t_k, v_k \le 99999$). $t_k$는 $k$번 치타가 출발하는 시각이고 $v_k$는 그 치타의 속력이다.

입력의 마지막 줄에는 $0$이 하나 주어진다. 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 무리 길이의 최솟값을 한 줄에 출력한다. 소수점 아래 넷째 자리에서 반올림하고, 소수점 아래 세 자리를 끝의 $0$까지 빠짐없이 적는다.