Problem: Despite urging requests of the townspeople, the municipal office cannot afford to improve many of the apparently deficient city amenities under this recession. The city swimming pool is one of the typical examples. It has only two swimming lanes. The Municipal Fitness Agency, under this circumstances, settled usage rules so that the limited facilities can be utilized fully.

Two lanes are to be used for one-way swimming of different directions. Swimmers are requested to start swimming in one of the lanes, from its one end to the other, and then change the lane to swim his/her way back. When he or she reaches the original starting end, he/she should return to his/her initial lane and starts swimming again.

Each swimmer has his/her own natural constant pace. Swimmers, however, are not permitted to pass other swimmers except at the ends of the pool; as the lanes are not wide enough, that might cause accidents. If a swimmer is blocked by a slower swimmer, he/she has to follow the slower swimmer at the slower pace until the end of the lane is reached. Note that the blocking swimmer’s natural pace may be faster than the blocked swimmer; the blocking swimmer might also be blocked by another swimmer ahead, whose natural pace is slower than the blocked swimmer. Blocking would have taken place whether or not a faster swimmer was between them.

Swimmers can change their order if they reach the end of the lane simultaneously. They change their order so that ones with faster natural pace swim in front. When a group of two or more swimmers formed by a congestion reaches the end of the lane, they are considered to reach there simultaneously, and thus change their order there.

The number of swimmers, their natural paces in times to swim from one end to the other, and the numbers of laps they plan to swim are given. Note that here one "lap" means swimming from one end to the other and then swimming back to the original end. Your task is to calculate the time required for all the swimmers to finish their plans. All the swimmers start from the same end of the pool at the same time, the faster swimmers in front.

In solving this problem, you can ignore the sizes of swimmers' bodies, and also ignore the time required to change the lanes and the order in a group of swimmers at an end of the lanes.



Input

The input is a sequence of datasets. Each dataset is formatted as follows.

n
t1 c1
...
tn cn


n is an integer (1 ≤ n ≤ 50) that represents the number of swimmers. ti and ci are integers (1 ≤ ti ≤ 300, 1 ≤ ci ≤ 250) that represent the natural pace in times to swim from one end to the other and the number of planned laps for the i-th swimmer, respectively. ti and ci are separated by a space.

The end of the input is indicated by a line containing one zero.

Output

For each dataset, output the time required for all the swimmers to finish their plans in a line. No extra characters should occur in the output.

Example

Input

2
10 30
15 20
2
10 240
15 160
3
2 6
7 2
8 2
4
2 4
7 2
8 2
18 1
0


Output

600
4800
36
40

Solution (in CPP):

Solution:
#define  _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-5L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define seg_size 262144LL
#define MOD 998244353LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

// geometry library

typedef complex<long double> Point;
typedef pair<complex<long double>, complex<long double>> Line;

typedef struct Circle {
    complex<long double> center;
    long double r;
}Circle;

//内積、 dot(a,b) = |a||b|cos()
long double dot(Point a, Point b) {
    return (a.real() * b.real() + a.imag() * b.imag());
}
//外積、cross(a,b) = |a||b|sin()
long double cross(Point a, Point b) {
    return (a.real() * b.imag() - a.imag() * b.real());
}

//線分と点の距離
long double Dist_Line_Point(Line a, Point b) {
    if (dot(a.second - a.first, b - a.first) < eps) return abs(b - a.first);
    if (dot(a.first - a.second, b - a.second) < eps) return abs(b - a.second);
    return abs(cross(a.second - a.first, b - a.first)) / abs(a.second - a.first);
}

//線分の交差判定
int is_intersected_ls(Line a, Line b) {
    return (cross(a.second - a.first, b.first - a.first) * cross(a.second - a.first, b.second - a.first) < 0) &&
        (cross(b.second - b.first, a.first - b.first) * cross(b.second - b.first, a.second - b.first) < 0);
}

//線分の交点
Point intersection_l(Line a, Line b) {
    Point da = a.second - a.first;
    Point db = b.second - b.first;
    return a.first + da * cross(db, b.first - a.first) / cross(db, da);
}

//線分と線分の距離
long double Dist_Line_Line(Line a, Line b) {
    if (is_intersected_ls(a, b) == 1) {
        return 0;
    }
    return min({ Dist_Line_Point(a,b.first), Dist_Line_Point(a,b.second),Dist_Line_Point(b,a.first),Dist_Line_Point(b,a.second) });
}

//円と円の交点
pair<Point, Point> intersection_Circle_Circle(Circle a, Circle b) {
    long double dist = abs(a.center - b.center);
    assert(dist <= eps + a.r + b.r);
    assert(dist+eps >= abs(a.r - b.r));
    Point target = b.center - a.center;
    long double pointer = target.real() * target.real() + target.imag() * target.imag();
    long double aa = pointer + a.r * a.r - b.r * b.r;
    aa /= 2.0L;
    Point l{ (aa * target.real() + target.imag() * sqrt(pointer * a.r * a.r - aa * aa))/pointer,
            (aa* target.imag() - target.real() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer};
    Point r{ (aa * target.real() - target.imag() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer,
        (aa * target.imag() + target.real() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer };
    r = r + a.center;
    l = l + a.center;
    return mp(l, r);
}

//end of geometry

template<typename A>
A pows(A val, ll b) {
    assert(b >= 1);
    A ans = val;
    b--;
    while (b) {
        if (b % 2) {
            ans *= val;
        }
        val *= val;
        b /= 2LL;
    }
    return ans;
}

template<typename A>
class Compressor {
public:
    bool is_zipped = false;
    map<A, ll> zipper;
    map<ll, A> unzipper;
    queue<A> fetcher;
    Compressor(){
        is_zipped = false;
        zipper.clear();
        unzipper.clear();
    }
    void add(A now) {
        assert(is_zipped == false);
        zipper[now] = 1;
        fetcher.push(now);
    }
    void exec() {
        assert(is_zipped == false);
        int cnt = 0;
        for (auto i = zipper.begin(); i != zipper.end(); ++i) {
            i->second = cnt;
            unzipper[cnt] = i->first;
            cnt++;
        }
        is_zipped = true;
    }
    ll fetch() {
        assert(is_zipped == true);
        A hoge = fetcher.front();
        fetcher.pop();
        return zipper[hoge];
    }
    ll zip(A now) {
        assert(is_zipped == true);
        assert(zipper.find(now) != zipper.end());
        return zipper[now];
    }
    A unzip(ll a) {
        assert(is_zipped == true);
        assert(a < unzipper.size());
        return unzipper[a];
    }
    ll next(A now) {
        auto x = zipper.upper_bound(now);
        if (x == zipper.end()) return zipper.size();
        return (ll)((*x).second);
    }
    ll back(A now) {
        auto x = zipper.lower_bound(now);
        if (x == zipper.begin()) return -1;
        x--;
        return (ll)((*x).second);
    }
};

template<typename A>
class Matrix {
public:
    vector<vector<A>> data;
    Matrix(vector<vector<A>> a) :data(a){

    }
    Matrix operator + (const Matrix obj) {
        vector<vector<A>> ans;
        assert(obj.data.size() == this->data.size());
        assert(obj.data[0].size() == this->data[0].size());
        REP(i, obj.data.size()) {
            ans.push_back(vector<A>());
            REP(q, obj.data[i].size()) {
                A hoge = obj.data[i][q] + (this -> data[i][q]);
                ans.back().push_back(hoge);
            }
        }
        return Matrix(ans);
    }
    Matrix operator - (const Matrix obj) {
        vector<vector<A>> ans;
        assert(obj.data.size() == this->data.size());
        assert(obj.data[0].size() == this->data[0].size());
        REP(i, obj.data.size()) {
            ans.push_back(vector<A>());
            REP(q, obj.data[i].size()) {
                A hoge = this->data[i][q] - obj.data[i][q];
                ans.back().push_back(hoge);
            }
        }
        return Matrix(ans);
    }
    Matrix operator * (const Matrix obj) {
        vector<vector<A>> ans;
        assert(obj.data.size() == this->data[0].size());
        REP(i, this -> data.size()) {
            ans.push_back(vector<A>());
            REP(q, obj.data[0].size()) {
                A hoge = (this -> data[i][0]) * (obj.data[0][q]);
                for(int t = 1;t < obj.data[i].size();++t){
                    hoge += this -> data[i][t] * obj.data[t][q];
                }
                ans.back().push_back(hoge);
            }
        }
        return Matrix(ans);
    }
    Matrix &operator *= (const Matrix obj) {
        *this = (*this * obj);
        return *this;
    }
    Matrix& operator += (const Matrix obj) {
        *this = (*this + obj);
        return *this;
    }
    Matrix& operator -= (const Matrix obj) {
        *this = (*this - obj);
        return *this;
    }
};

class modint {
public:
    using u64 = std::uint_fast64_t;
    u64 value = 0;
    u64 mod;
    modint(ll a, ll b): value(((a%b) + 2 * b) % b),mod(b) {

    }
    modint operator+(const modint rhs) const{
        return modint(*this) += rhs;
    }
    modint operator-(const modint rhs) const{
        return modint(*this) -= rhs;
    }
    modint operator*(const modint rhs) const {
        return modint(*this) *= rhs;
    }
    modint operator/(const modint rhs) const{
        return modint(*this) /= rhs;
    }
    modint& operator+=(const modint rhs) {
        assert(rhs.mod == mod);
        value += rhs.value;
        if (value >= mod) {
            value -= mod;
        }
        return *this;
    }
    modint& operator-=(const modint rhs) {
        assert(rhs.mod == mod);
        if (value < rhs.value) {
            value += mod;
        }
        value -= rhs.value;
        return *this;
    }
    modint& operator*=(const modint rhs) {
        assert(rhs.mod == mod);
        value = (value *  rhs.value) % mod;
        return *this;
    }
    modint& operator/=(modint rhs) {
        assert(rhs.mod == mod);
        ll rem = mod - 2;
        while (rem) {
            if (rem % 2) {
                *this *= rhs;
            }
            rhs *= rhs;
            rem /= 2LL;
        }
        return *this;
    }
    friend ostream& operator<<(ostream& os, modint& p) {
        os << p.value;
        return (os);
    }
};

void init() {
    iostream::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}

unsigned long xor128() {
    static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned long t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

#define int ll

void solve(){
    while (true) {
        int n;
        cin >> n;
        if (n == 0) return;
        queue<tuple<int, int, int>> next[2];
        int now_time = 0;
        vector<pair<int, int>> inputs;
        REP(i, n) {
            int a, b;
            cin >> a >> b;
            inputs.push_back(mp(a, b));
        }
        sort(ALL(inputs));
        REP(i, n) {
            next[0].push(make_tuple(inputs[i].first, inputs[i].first, inputs[i].second));
        }
        while (next[0].empty() == false || next[1].empty() == false) {
            int target = 0;
            if (next[0].empty() == true) {
                target = 1;
            }
            else if (next[1].empty() == true) {
                target = 0;
            }
            else {
                if (get<0>(next[0].front()) < get<0>(next[1].front())) {
                    target = 0;
                }
                else {
                    target = 1;
                }
            }
            vector<pair<int, int>> now;
            int limit = get<0>(next[target].front());
            while (next[target].empty() == false && get<0>(next[target].front()) <= limit) {
                now.push_back(mp(get<1>(next[target].front()), get<2>(next[target].front()) - target));
                next[target].pop();
            }
            sort(ALL(now));
            now_time = limit;
            REP(q, now.size()) {
                if (now[q].second == 0) continue;
                next[(target + 1) % 2].push(make_tuple(limit + now[q].first, now[q].first, now[q].second));
            }
        }
        cout << now_time << endl;
    }
}

#undef int
int main() {
    init();
    solve();
}