수영장 정체

주민들의 간곡한 요청에도 불구하고, 시청은 이 불황 속에서 낡아 보이는 여러 시설을 개선할 여력이 없다. 시립 수영장이 그 대표적인 예이다. 이 수영장에는 수영 레인이 단 두 개뿐이다. 이러한 상황에서 시립 체육공단은 한정된 시설을 최대한 활용할 수 있도록 이용 규칙을 정하였다.

두 레인은 서로 다른 방향으로 헤엄치는 일방통행용으로 사용된다. 수영자는 두 레인 중 하나에서 출발하여 한쪽 끝에서 반대쪽 끝까지 헤엄친 다음, 레인을 바꿔 되돌아오도록 요청받는다. 원래 출발했던 끝에 도달하면 처음 레인으로 돌아가 다시 헤엄치기 시작해야 한다.

각 수영자는 자신만의 일정한 고유 속도를 가진다. 그러나 레인이 충분히 넓지 않아 사고가 날 수 있기 때문에, 수영자는 수영장의 양 끝을 제외하고는 다른 수영자를 추월할 수 없다. 어떤 수영자가 더 느린 수영자에게 막히면, 그 레인의 끝에 도달할 때까지 느린 수영자를 느린 속도로 뒤따라가야 한다. 이때 막고 있는 수영자의 고유 속도가 막힌 수영자보다 빠를 수도 있다는 점에 유의하라. 또한 막고 있는 수영자 자신도, 고유 속도가 막힌 수영자보다 더 느린 앞선 또 다른 수영자에게 막혀 있을 수 있다. 두 수영자 사이에 더 빠른 수영자가 있든 없든 막힘은 일어난다.

수영자들은 레인의 끝에 동시에 도달한 경우에만 순서를 바꿀 수 있다. 이때 고유 속도가 더 빠른 수영자가 앞서도록 순서를 바꾼다. 정체로 인해 형성된, 두 명 이상의 수영자로 이루어진 무리가 레인의 끝에 도달하면 그들은 동시에 도달한 것으로 간주되어 그곳에서 순서를 바꾼다.

수영자의 수, 한쪽 끝에서 반대쪽 끝까지 헤엄치는 데 걸리는 시간으로 표현된 각 수영자의 고유 속도, 그리고 각자가 헤엄칠 계획인 랩 수가 주어진다. 여기서 한 "랩"은 한쪽 끝에서 반대쪽 끝까지 헤엄친 뒤 다시 원래 끝으로 되돌아오는 것을 뜻한다는 점에 유의하라. 모든 수영자가 계획을 마치는 데 필요한 시간을 구하는 것이 당신의 과제이다. 모든 수영자는 같은 끝에서 동시에 출발하며, 더 빠른 수영자가 앞에 선다.

이 문제를 풀 때, 수영자의 몸 크기는 무시해도 되며, 레인을 바꾸는 시간과 레인 끝에서 무리 안의 순서를 바꾸는 데 걸리는 시간도 무시해도 된다.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다.

n
t1 c1
. . .
tn cn

$n$은 수영자의 수를 나타내는 정수이다 ($1 \le n \le 50$). $t_i$와 $c_i$는 각각 $i$번째 수영자의 고유 속도(한쪽 끝에서 반대쪽 끝까지 헤엄치는 데 걸리는 시간)와 계획한 랩 수를 나타내는 정수이다 ($1 \le t_i \le 300$, $1 \le c_i \le 250$). $t_i$와 $c_i$는 공백으로 구분된다.

입력의 끝은 하나의 $0$만 있는 줄로 표시된다.

각 데이터셋에 대해, 모든 수영자가 계획을 마치는 데 필요한 시간을 한 줄에 출력한다. 출력에 그 외의 문자가 나타나서는 안 된다.