Shawarma Menu

Time limit: 0.5 s.
Memory limit: 256 MB

A true price for one shawarma is \(X\) riyals (integer), but nobody buys just one shawarma. That’s why Humaid’s shawarma truck lists its menu as follows.

The menu has \(N\) items of the form “\(Q\) shawarmas for \(P\) riyals”, where \(P\) is \(Q \cdot X\) rounded to the nearest thousand.

For example, if \(X\) is \(67\) then the menu could be

  • \(100\) shawarmas for \(7000\) sar
  • \(200\) shawarmas for \(13000\) sar
  • \(300\) shawarmas for \(20000\) sar
  • \(512\) shawarmas for \(34000\) sar

Input

First line has a single integer \(N\) the number of menu items. \((1 \le N \le 10^5)\)

Each of next \(N\) lines contains two integers: \(Q_i\), \(P_i\) quantity and price for \(i_{th}\) menu item. \((1 \le Q_i \le 10^9), (1000 \le P_i \le 10^9)\) Its guaranteed that \(P_i\) is a multiple of \(1000\).

Output

The minimum possible value of \(X\) – the true price for one shawarma. It is guaranteed that \(X \le 10^9\)

Scoring

Subtask Constraints Points
\(1\) \(N = 1\) \(10\)
\(2\) \(N = 2\) \(20\)
\(3\) \(N \le 1000, X \le 1000\) \(30\)
\(4\) \(1000 \lt N \le 10^5\) \(40\)

Example

Input

2
100 7000
200 13000

Output

65

Note

Rounding an integer if \(Z\) to nearest thousand works by checking \(Z\) divided by \(1000\) has remainder of less than \(500\), then \(P = \lfloor \frac{Z}{1000} \rfloor \cdot 1000\), otherwise \(P = \lceil \frac{Z}{1000} \rceil \cdot 1000\).

Solution

A price rounds to \(P_i\) exactly when

\[ P_i-500 \le Q_iX < P_i+500. \]

Because \(X\) is an integer, the smallest value allowed by this menu item is

\[ \left\lceil\frac{P_i-500}{Q_i}\right\rceil. \]

\(X\) must satisfy every item, so the answer is the maximum of these lower bounds. The statement guarantees that the resulting constraints are consistent.

The complexity is \(O(N)\) time and \(O(1)\) memory.

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long answer = 0;

    while (n--) {
        long long quantity, price;
        cin >> quantity >> price;

        long long minimumPrice =
            (price - 500 + quantity - 1) / quantity;
        answer = max(answer, minimumPrice);
    }

    cout << answer << '\n';
}