Homer Simpson

Nguồn: UVa

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

Đề bài

Homer có $t$ phút. Một loại burger mất $m$ phút, loại còn lại mất $n$ phút. Ưu tiên để thời gian uống bia còn lại nhỏ nhất; với cùng thời gian còn lại, ăn nhiều burger nhất. Nếu không còn thời gian thừa, chỉ in số burger; nếu còn, in thêm số phút uống bia.

Input

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

Output

In số burger tối đa theo tiêu chí trên; nếu còn thời gian thừa thì in thêm số phút thừa trên cùng dòng.

Subtask

• Subtask 1 — 20 điểm: m,n,t <= 100. Mức này dành cho cách trực tiếp hoặc đệ quy nhỏ.
• Subtask 2 — 30 điểm: m,n,t <= 2000. Mức này yêu cầu nhận ra trạng thái DP và loại bỏ tính toán lặp.
• Subtask 3 — 50 điểm: 0 < m,n,t < 10000. Đây là toàn bộ giới hạn của bài.

Ví dụ

Input

3 5 54

Output

18

Giải thích

$54$ chia hết thành $18$ phần dài 3 phút, nên Homer ăn 18 burger và không còn phút uống bia.