题目描述

饭堂有一个卖肠粉的窗口，窗口里有一位阿姨负责制作肠粉。阿姨不会提前制作肠粉，只有在同学到达窗口并点餐后，才会开始为该同学制作肠粉。

阿姨制作一份肠粉需要经过两个步骤：

• 先花费 $t_1$ 时间处理原材料；
• 然后把处理好的原材料放进肠粉机中蒸煮，蒸煮需要花费 $t_2$ 时间。

蒸煮完成后，这份肠粉就可以立刻交付给对应的同学。

阿姨一次只能处理 $1$ 份原材料。饭堂窗口有 $2$ 台肠粉机，每台肠粉机一次只能蒸煮 $1$ 份肠粉。

注意，阿姨处理原材料和肠粉机蒸煮是相互独立的。也就是说，当两台肠粉机正在蒸煮肠粉时，阿姨仍然可以继续处理其他同学的原材料。处理好的原材料如果暂时没有空闲的肠粉机，可以等待肠粉机空闲后再开始蒸煮。

如果阿姨空闲时有多名同学正在等待，则阿姨会优先为最早到达的同学处理原材料。

一共有 $n$ 个同学来购买肠粉。第 $i$ 个同学会在 $i^2$ 时刻到达窗口并点一份肠粉。

每个同学的等待时间定义为：

请你求出 $n$ 个同学的等待时间总和。

输入格式

输入一行，包含三个正整数 $t_1, t_2, n$，分别表示处理原材料所需时间、蒸煮所需时间和同学数量。

输出格式

输出一行，包含一个正整数，表示所有同学的等待时间总和。

样例

3 7 10

100

10 1 10

194

样例解释

样例 1：第 $1$ 个同学在 $1^2=1$ 时刻到达，第 $2$ 个同学在 $2^2=4$ 时刻到达，依此类推。在本样例中，每位同学从到达到拿到肠粉都需要等待 $10$ 时间，因此总等待时间为 $10 \times 10 = 100$。

样例 2：本样例中，处理原材料所需时间较长，而蒸煮所需时间较短。因此主要的等待来自阿姨处理原材料的排队。按照规则模拟每位同学从到达、处理原材料、进入肠粉机蒸煮直到拿到肠粉的过程，可以得到总等待时间为 $194$。

数据范围

对于所有数据，保证 $1 \le t_1, t_2, n \le 10^5$。第 $i$ 个同学在 $i^2$ 时刻到达窗口。

要获得满分，程序需要正确处理 $64$ 位整数（例如在 C/C++ 中使用 long long 类型）。