テンキー (Tenkey)

JOI 君はテンキーを \(1\) つ持っている．このテンキーには \(0\) から \(9\) までの数字が印字されているキーが以下の図のように配置されている． \(2\) が印字されたキーの下，および \(3\) が印字されたキーの下にはキーは存在しないことに注意せよ．

またこのテンキーには，テンキーに配置されているキーのうち \(1\) つのキーを指し示すカーソルが存在している．カーソルは最初 \(0\) が印字されているキーを指し示している．

JOI 君は \(1\) 回の操作で次のうちのいずれかを選んで行うことができる：

• カーソルを，現在カーソルが指し示しているキーと上下左右に隣接しているキーに移動させる．ただし，キーが存在しない場所にカーソルを移動させることはできない．
• キーを押す．すなわち，カーソルが指し示しているキーに印字されている数字を入力する．この際，以前の操作によってすでに数字が入力されていた場合，すでに入力されていた数字のすぐ右に新たな数字が入力される．

いま，JOI 君はこのテンキーを使って， \(M\) で割った余りが \(R\) であるような正の整数を入力したいと考えている．テンキーの操作には時間がかかるので，なるべく少ない操作回数で入力したい．

\(M\) と \(R\) が与えられるので，JOI 君が行う必要のある操作の回数の最小値を求めるプログラムを作成せよ．

• \(2 \leqq M \leqq 100\,000\)．
• \(1 \leqq R < M\)．
• 入力される値はすべて整数である．

1. (\(30\) 点) \(M = 100\,000\)．
2. (\(70\) 点) 追加の制限はない．

入力は以下の形式で標準入力から与えられる．

\(M\) \(R\)

\(M\) で割った余りが \(R\) であるような正の整数を入力するために必要な操作の回数の最小値を \(1\) 行で出力せよ．

JOI 2020 · JCIOI · CC BY-SA 4.0