Лягушка изначально находится в позиции \(0\) на числовой прямой. У лягушки есть два положительных числа \(a\) и \(b\). Из позиции \(k\) он может перейти либо в позицию \(k+a\), либо в \(k-b\).
Пусть \(f(x)\) — количество различных целых чисел, координаты которых лягушка может достичь, если она всегда будет находиться в интервале \([0, x]\). Лягушке не нужно посещать все эти числа за один раз, то есть число считается, если лягушка может каким-то образом достичь его, если она начинает с \(0\).
Дается число \(m\), найдите \(\sum_{i=0}^{m} f(i)\). Другими словами, найдите сумму по всем \(f(i)\) для всех \(i\) от \(0\) до \(m\).
Выходные данные
Выведите одно целое число — искомую сумму.
Примечание
В первом примере нам нужно найти \(f(0)+f(1)+\ldots+f(7)\). У нас есть \(f(0) = 1, f(1) = 1, f(2) = 1, f(3) = 1, f(4) = 1, f(5) = 3, f(6) = 3, f(7) = 8\). Сумма этих чисел равна \(19\).
Во втором примере \(f(i) = i+1\), то есть нужно найти сумму \(\sum_{i=0}^{10^9} i+1\).
В третьем примере лягушка не может прыгать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 5 3
|
19
|
|
2
|
1000000000 1 2019
|
500000001500000001
|
|
3
|
100 100000 1
|
101
|
|
4
|
6 4 5
|
10
|