En ce jour de fête nationale dans le royaume H, le roi invite n dignitaires à participer à un jeu récompensé.

Chaque dignitaire note un nombre entier sur sa main gauche et un sur sa main droite. Le roi fait de même.

Les n dignitaires forment ensuite une file, avec le roi en tête.

Chaque dignitaire reçoit un certain nombre de pièces d'or, calculé comme le quotient entier du produit des nombres sur les mains gauches de tous ceux qui le précèdent, divisé par le nombre sur sa propre main droite.

Le roi souhaite que la récompense maximale accordée à un dignitaire soit la plus faible possible. Il vous demande de déterminer l'arrangement optimal de la file.

Format d'entrée

La première ligne contient un entier n, le nombre de dignitaires.

La deuxième ligne contient deux entiers a et b, séparés par un espace, représentant les nombres sur les mains gauche et droite du roi.

Les n lignes suivantes contiennent chacune deux entiers a et b, séparés par un espace, représentant les nombres sur les mains gauche et droite de chaque dignitaire.

Format de sortie

Une seule ligne contenant un entier : la récompense maximale minimale possible parmi les dignitaires dans l'arrangement optimal.

Contranites

1 ≤ n ≤ 1000
0 < a, b < 10000

Exemple

Entrée :

3
1 1
2 3
7 4
4 6

Sortie :

2

Approche algorithmique

Considérons deux dignitaires adjacents i et i+1. La récompense de chaque dignitaire dépend du produit des nombres sur les mains gauches de tous les précédents divisé par son propre nombre de main droite.

Propriété 1 : Si a_i × b_i ≥ a_{i+1} × b_{i+1}, alors échanger i et i+1 ne peut pas augmenter la récompense maximale.

Propriété 2 : L'arrangement optimal satisfait a_i × b_i ≤ a_{i+1} × b_{i+1} pour toute paire adjacente.

Concluison : Trier les dignitaires par la valeur croissante de a × b donne l'arrangement optimal.

Implémentation en code

Le produit des nombres sur les mains gauches peut devenir très grand, nécessitant une arithmétique à précision arbitraire. On représente les grands nombres par des vecteurs de chiffres en base 10, avec l'unité à l'indice 0.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Official {
    long long left;
    long long right;
};

vector<int> multiplyBigNumber(const vector<int>& bigNum, int factor) {
    vector<int> result;
    int carry = 0;
    for (size_t i = 0; i < bigNum.size() || carry; ++i) {
        if (i < bigNum.size()) {
            carry += bigNum[i] * factor;
        }
        result.push_back(carry % 10);
        carry /= 10;
    }
    return result;
}

vector<int> divideBigNumber(const vector<int>& bigNum, int divisor) {
    vector<int> reversedNum(bigNum.rbegin(), bigNum.rend());
    vector<int> quotient;
    long long remainder = 0;
    for (int digit : reversedNum) {
        remainder = remainder * 10 + digit;
        quotient.push_back(remainder / divisor);
        remainder %= divisor;
    }
    reverse(quotient.begin(), quotient.end());
    while (quotient.size() > 1 && quotient.back() == 0) {
        quotient.pop_back();
    }
    return quotient;
}

vector<int> maxBigNumber(const vector<int>& a, const vector<int>& b) {
    if (a.size() != b.size()) {
        return a.size() > b.size() ? a : b;
    }
    for (int i = a.size() - 1; i >= 0; --i) {
        if (a[i] != b[i]) {
            return a[i] > b[i] ? a : b;
        }
    }
    return a;
}

int main() {
    int n;
    long long kingLeft, kingRight;
    cin >> n >> kingLeft >> kingRight;

    vector<Official> officials(n);
    for (int i = 0; i < n; ++i) {
        cin >> officials[i].left >> officials[i].right;
    }

    // Tri selon le produit croissant de gauche et droite
    sort(officials.begin(), officials.end(), [](const Official& x, const Official& y) {
        return x.left * x.right < y.left * y.right;
    });

    // Conversion du nombre initial (produit des gauches du roi) en representation à précision arbitraire
    vector<int> cumulativeProduct;
    long long temp = kingLeft;
    while (temp) {
        cumulativeProduct.push_back(temp % 10);
        temp /= 10;
    }

    vector<int> maxReward;
    for (const auto& off : officials) {
        // Calcul de la récompense du dignitaire courant
        vector<int> currentReward = divideBigNumber(cumulativeProduct, off.right);
        maxReward = maxBigNumber(maxReward, currentReward);
        // Mise à jour du produit cumulé
        cumulativeProduct = multiplyBigNumber(cumulativeProduct, off.left);
    }

    // Affichage du résultat
    for (auto it = maxReward.rbegin(); it != maxReward.rend(); ++it) {
        cout << *it;
    }
    cout << endl;

    return 0;
}