题目描述

给定$n,a,b$，有一个大小为$n*n$的网格，坐标$(i,j)$上的权值为$gcd(i,a)+gcd(j,b)$。

梦梦初始时站在$(1,1)$，每次他可以往下或往右走一格，不能走到$n*n$网格外部，直至走到$(n,n)$位置，梦梦想知道他经过的所有网格的权值之和最小可以是多少。

输入格式

第一行三个正整数$n,a,b$。

输出格式

输出一行，表示答案

样例

4 2 4

21

样例1解释： 网格值为 2 3 2 5 3 4 3 6 2 3 2 5 3 4 3 6 最优解为(1,1),(2,1),(3,1),(3,2),(3,3),(4,3),(4,4) 值和为2+3+2+3+2+3+6=21

10 210 420

125

100000 210 420

2149789

数据范围

对于30%的数据，$1\leq{n,a,b}\leq{5}$ 对于60%的数据，$1\leq{n,a,b}\leq{1000}$ 对于100%的数据，$1\leq{n,a,b}\leq{10^6}$