Class

Interview

Time limit3sMemory limit256 MB

Summary

Given n students and an r by c grid of desks, find the maximum achievable value k such that some row and some column can each have k occupied desks.

Level: Medium4 of 10
Topics: Math, Greedy, Binary search
Solved: No attempts yet

Problem

Dr. Strange is a very strange lecturer. During each lecture he computes the class fullness, and if it turns out to be small he lowers everyone's grade for the semester by one. Naturally, the students want to make the class fullness as large as possible.

The class fullness is the minimum of the row fullness and the column fullness:

The column fullness is the maximum number of students sitting in any single column.
The row fullness is the maximum number of students sitting in any single row.

For example, suppose 16 students are seated as in the left picture below (occupied desks are darkened). The row fullness is 5 (the 4th row) and the column fullness is 3 (achieved by the 1st, 3rd, 5th or 6th column), so the class fullness is 3. If the students rearrange themselves as in the right picture, the column fullness becomes 4 (the 5th column), so the class fullness also becomes 4.

The classroom has r rows and c columns of desks (r × c desks in total), and there are n students. Each desk seats at most one student and all n students must be seated. Determine the largest class fullness the students can achieve.

Input

The first line contains three integers n, r and c — the number of students, the number of rows, and the number of columns in the classroom (1 ≤ r, c ≤ 100, 1 ≤ n ≤ r × c).

Output

Print a single integer — the maximum possible class fullness.

Examples4

Example 1
Input
```
16 4 6
```
Expected output
```
4
```
Example 2
Input
```
1 1 1
```
Expected output
```
1
```
Example 3
Input
```
3 2 2
```
Expected output
```
2
```
Example 4
Input
```
10000 100 100
```
Expected output
```
100
```