Description

本题的主角收到了神奇药丸的邮件推销，这些药丸据说能极大提升他的认知和各种能力。在仔细分析了所有的优惠和副作用后，他决定只订购两种药丸，分别称为 $A$ 和 $B$。他需要每隔 $k$ 天服用一次药丸 $A$，每隔 $j$ 天服用一次药丸 $B$。在接下来的 $n$ 天里，他会严格遵守这个计划。

更正式地说，在接下来的 $n$ 天中，不能有连续 $k$ 天没有服用药丸 $A$，也不能有连续 $j$ 天没有服用药丸 $B$。然而，还有一个限制——这两种药丸药效极强，绝不能在同一天服用，否则会产生严重的副作用。给定这些限制，问他最少需要服用多少颗药丸才能满足要求？

Input Format

输入包含三个用空格分隔的整数，$k$、$j$ 和 $n$。

Output Format

输出一个整数，表示满足要求所需服用的最少药丸数。可以证明，对于给定的限制条件，总是存在解。

2 3 8

6

2 3 11

9

3 7 100

48

Hint

说明

在第一个样例中，可以在第 $2$、$4$、$5$ 和 $7$ 天服用药丸 $A$，在第 $3$ 和 $6$ 天服用药丸 $B$，得到的序列为 $\text{.ABAABA}$。在第二个样例中，最优方案是序列 $\text{.ABAABAABA}$，共需要服用 $9$ 颗药丸。

输入范围

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

由 ChatGPT 4.1 翻译