题目描述

An unnamed protagonist of this task received amazing e-mail offers for wondrous pills that will enhance their cognitive and all other sorts of abilities. After carefully analysing all offers and side effects, he has decided that he will order 2 types of pills, let's call them $A$ and $B$. He needs to take pill $A$ every $k$ days and pill $B$ every $j$ days. He will follow this meticulously over the next $n$ days.

More formally, in the next $n$ days, there should be no $k$ consecutive days where he does not take pill $A$ and no $j$ consecutive days where pill $B$ is not taken. However, there is a twist – the two pills are highly potent and must not be taken on the same day, lest horrible side effects should happen. Given this constraint, what is the smallest number of pills that he needs to take to meet these requirements?

输入格式

You are given three space-separated integers, $k$, $j$, and $n$.

输出格式

Print one number – the minimum number of pills that need to be taken. It is easy to prove that a solution always exists for the given constraints.

2 3 8

6

2 3 11

9

3 7 100

48

提示

Comment

In the first case, we can take pill $A$ on days $2$, $4$, $5$, and $7$, and pill $B$ on days $3$ and $6$, giving the sequence $\text{.ABAABA}$. In the second case, the best approach is to take pills in sequence $\text{.ABAABAABA}$, which requires taking $9$ pills.

Input limits

• $2 \leq n \leq 10^6$
• $2 \leq k, j \leq n$