Problem Description

Given $a,\,b,\,c$, find the number of non-negative integer solutions that satisfy the inequality $ax+by \leqslant c$.

Input Format

Input three integers $a,\,b,\,c$.

Output Format

Output one integer representing the answer.

3 4 13

12

Hint

Sample Explanation:

Let $(x,\,y)$ represent a valid solution. The sample has the following $12$ valid solutions:

$(0,\,0)$, $(0,\,1)$, $(0,\,2)$, $(0,\,3)$, $(1,\,0)$, $(1,\,1)$, $(1,\,2)$, $(2,\,0)$, $(2,\,1)$, $(3,\,0)$, $(3,\,1)$, $(4,\,0)$.

Constraints:

For all testdata, $1 \leqslant a,\,b \leqslant 10^9,\ 0 \leqslant c \leqslant \min(a,\,b) \times 10^9$.

Translated by ChatGPT 5