Cakes

Interview

Time limit1sMemory limit512 MB

Summary

Given how much of each of N ingredients one cake needs and how much you have, find the largest number of cakes you can bake.

Level: Easy2 of 10
Topics: Implementation, Math, Brute force
Solved: No attempts yet

Problem

This summer you plan to hold a big party and invite many friends. They have a sweet tooth, so you intend to bake nice cakes for them. You know the recipe for a nice chocolate cake, and you want to make as many of them as possible.

Given the $N$ ingredients needed to make a single cake and the amounts of those ingredients you have in your kitchen, determine how many cakes you can make.

Input

The first line contains a single integer $N$ .
Then $N$ lines follow, one for each ingredient. Each line contains two positive integers: the first is the amount of this ingredient needed per cake, and the second is the amount of this ingredient you have in your kitchen.

Output

Print a single integer: the maximum number of cakes you can make with the available ingredients.

Constraints

$1 \leq N \leq 10$
Every ingredient amount is an integer between $1$ and $10\,000$ .

Examples2

Example 1
Input
```
3
100 500
2 5
70 1000
```
Expected output
```
2
```
Example 2
Input
```
3
100 50
2 5
70 1000
```
Expected output
```
0
```