题目描述

U酱准备前往阿卡胡拉取材。然而她发现这里的过路费很贵。

U酱从 $(0, 0)$ 启程，要前往目的地 $(x, y)$。当她处于 $(i,j)$ 时，她下一步可以前往 $(i+1,j)$ 或者 $(i,j+1)$。每当她来到一个新的整点 $(i,j)$，需要缴纳 $gcd(i,j)$ 的过路费。注意 $gcd(0, x)=x$。

U酱想要知道，从 $(0, 0)$ 到 $(x, y)$ 的所有合法路径中，她需要缴纳的最少过路费是多少？

输入格式

第一行两个正整数 $x, y$。

输出格式

输出一个整数表示答案。

9 4

15

7 7

20

133 140

279

242848086 739639966

982488080

数据范围

Subtask $1$（$18$ pts）：保证 $xy \leqslant 10^6$。

Subtask $2$（$1$ pts）：保证 $\min(x, y)=0$。

Subtask $3$（$2$ pts）：保证 $x \leqslant y$，且 $y$ 是质数。

Subtask $4$（$6$ pts）：保证 $x+10^5 < y < 2x$，且 $x$ 是质数。

Subtask $5$（$39$ pts）：保证 $\min(x, y) \leqslant 10^6$。

Subtask $6$（$34$ pts）：无特殊限制。

对于 $100\%$ 的数据，保证 $0 \leqslant x, y \leqslant 10^9$。