K. Fallout Van Buren: Wasteland Survival
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're playing Fallout Van Buren, an unreleased post-apocalyptic RPG. In this version, character builds are simplified to two stats: Strength (S) and Armor (E). Strength determines your damage output, while Armor represents your Power Armor's integrity.

You're about to face N hostile creatures in the wasteland. Each enemy i has damage $$$A_i$$$ and armor $$$D_i$$$.

Combat Mechanics:

  • Combat is turn-based; you always strike first

  • Each attack reduces the target's armor by the attacker's Strength

  • A combatant is defeated when they receive an attack while their armor is already at zero — think of it as your Power Armor absorbing hits until it breaks, then the next hit is fatal

  • Your Power Armor fully repairs between encounters

  • Stats are assigned once and cannot be changed
You have $$$X$$$ points to distribute between $$$S$$$ and $$$E$$$ (both start at zero).

Find the minimum $$$X$$$ such that you can defeat all $$$N$$$ enemies.

Input

The first line contains a single integer N $$$(1 \leq N \leq 1000)$$$.

Each of the next N lines contains two integers $$$A_i$$$ and $$$D_i$$$ $$$(1 \leq A_i, D_i \leq 1000)$$$.

Output

Print a single integer, the minimum stat points $$$X$$$ needed.

Examples
Input
2
3 10
5 6
Output
10
Input
1
7 15
Output
16