Homer Simpson

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

Homer has $t$ minutes. One burger takes $m$ minutes and another takes $n$ minutes. First minimize unused beer time; among plans with the same unused time, maximize the number of burgers. If no time is left, print only the burger count; otherwise also print the beer time.

Input

The only line contains integers $m,n,t$.

Output

Print the optimal burger count; if there is unused time, also print that number of minutes on the same line.

Subtasks

• Subtask 1 — 20 points: m,n,t <= 100.
• Subtask 2 — 30 points: m,n,t <= 2000.
• Subtask 3 — 50 points: 0 < m,n,t < 10000.

Examples

Input

3 5 54

Output

18

Explanation

$54$ can be filled by eighteen 3-minute burgers, so Homer eats 18 burgers with no beer time.