配点 : 100 点

問題文

素数 K が与えられます。 空の数列があり、えびまちゃんはこの末尾に 1 から N までの整数を 1 個ずつ順に追加していきます。

ところで、のいみちゃんは長さ K の等差数列が嫌いです。えびまちゃんが整数 X を数列に追加したことで、部分列（連続とは限らない）として長さ K の等差数列が取れてしまうとき、X を即座に捨ててしまいます。

最終的に数列に含まれる要素の数を求めてください。

制約

• 1 \le N \le 10^{18}
• 2 \le K \le 100
• K は素数

入力例 1

5 2

出力例 1

1

えびまちゃんが 2 以降の整数 X を追加したとき、\left( 1, X \right) という長さ 2 の等差数列が出来てしまいます。

入力例 2

10 3

出力例 2

5

最終的な数列は \left(1, 2, 4, 5, 10\right) です。