Đóng gói hình chữ nhật (Packing Rectangles)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ hình chữ nhật giống hệt nhau, mỗi hình có chiều rộng $w$ và chiều cao $h$.

Các hình chữ nhật không được xoay. Cạnh rộng $w$ luôn song song với một cạnh của hình vuông, cạnh cao $h$ song song với cạnh còn lại. Các hình chữ nhật không được chồng lên nhau.

Hãy tìm độ dài cạnh nguyên nhỏ nhất $x$ của hình vuông sao cho có thể đặt đủ $n$ hình chữ nhật vào bên trong.

Input

Dòng duy nhất chứa ba số nguyên $w$, $h$, $n$.

Output

In độ dài cạnh nhỏ nhất của hình vuông.

Subtask

• Subtask 1 — 20%: $1\le w,h,n\le10^4$.
• Subtask 2 — 30%: $1\le w,h,n\le10^7$.
• Subtask 3 — 50%: $1\le w,h,n\le10^9$.

Ví dụ

Input

2 3 10

Output

9

Giải thích

Với $x=8$ chỉ xếp được $\lfloor8/2\rfloor\cdot\lfloor8/3\rfloor=8$ hình. Với $x=9$ xếp được $4\cdot3=12$ hình, đủ cho $10$ hình, nên đáp án là $9$.