题目描述

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

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

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

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

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

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

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

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

每个同学的等待时间定义为：拿到肠粉的时刻 $-$ 到达窗口的时刻。

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

约定和数据范围

对于所有数据，保证：

$1 \leq t1, t2, n \leq 10^5$

第 $i$ 个同学在 $i^2$ 时刻到达窗口。

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

格式

输入格式

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

输出格式

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

样例

3 7 10

100

10 1 10

194

样例解释

样例1解释：

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

样例2解释：

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