题目描述

Charley于时刻0到达起点，要骑车走完4500米。他必须有同方向的骑车者以相同速度陪伴。从起点等待到首个不早于0出发的陪伴者时刻，便可以与之出发；若此时有多个，可跟随更快者。途中若被更快的同路者追上，就立即换成该人的速度；若同时被多人追上，跟随最快者。换伴和变速不耗时，不停下等待更慢者。

所有同路者都从同一起点出发，以各自恒定速度沿同一路线骑到终点。第i人的速度v_i单位千米/小时，出发时刻t_i单位秒，可以为负，表示Charley到达前此人已经离开。负时刻出发的人不能在起点成为初始陪伴者。

求Charley到达终点相对于时刻0的时间，若不是整数秒，向上取整。若没有任何不早于0出发的陪伴者，输出-1。

输入

多组数据。每组先给n，再给n行v_i,t_i。n=0结束，不再有该组骑车者。

输出

每组一行，上述最早到达时间（含在起点等待），向上取整。

本地完整数据范围

1≤n≤10000；v_i为1..10000的整数，t_i为[-10^9,10^9]内整数；每份输入最多20组，总人数≤100000。结束标记0必须出现。

输入样例

4
20 0
25 -155
27 190
30 240
2
21 0
22 34
0

输出样例

780
771

本地修订说明

原页未限制速度/时刻数值、未声明速度整数或小数、全负出发时无定义。本地规范正整数v≤10000、整数t±1e9、最多20组总10万人，输出含起点等待的相对0时刻；无可初始陪行者-1。将陪伴规则完整文字化，核心4500米/跟更快者/向上取整不变。

根据用户授权整理。本题使用公开样例与独立自编训练数据，非官方原版评测数据。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：原页未限制速度/时刻数值、未声明速度整数或小数、全负出发时无定义。本地规范正整数v≤10000、整数t±1e9、最多20组总10万人，输出含起点等待的相对0时刻；无可初始陪行者-1。将陪伴规则完整文字化，核心4500米/跟更快者/向上取整不变。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1227。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。