K. 网格行走
每次测试的时间限制：2 秒
每次测试的内存限制：512 兆字节

你有一个 $n \times n$ 的网格，以及两个整数 $a$ 和 $b$。行和列都从 $1$ 到 $n$ 编号。记第 $i$ 行第 $j$ 列的交点处的格子为 $(i,j)$。

你从格子 $(1,1)$ 出发，要移动到格子 $(n,n)$。

假设你在格子 $(i,j)$，每一步你可以移动到格子 $(i, j+1)$ 或 $(i+1, j)$（如果相应格子存在）。

定义格子 $(i,j)$ 的代价为：

其中 $\gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公约数。
一条从 $(1,1)$ 到 $(n,n)$ 的路径的代价是路径经过的所有格子的代价之和（包括起点和终点）。

找到代价最小的路径，并输出其代价。

输入
仅一行包含三个整数 $n$、$a$ 和 $b$（$2 \le n \le 10^6$；$1 \le a, b \le 10^6$）。

输出
输出一个整数 —— 从 $(1,1)$ 到 $(n,n)$ 的最便宜路径的代价。

示例

示例 1
输入

4 2 4

输出

21

示例 2
输入

10 210 420

输出

125

注释
第一个示例如上图所示。