便宜上、「文字列 \(S\) を \(K\) 個連結したプログラムを実行する」ことを「文字列 \(S\) を \(K\) 回繰り返し実行する」と解釈します。

文字列 \(S\) の \(1\) 回目の実行時の、ロボットの位置の変化を \((0, 0) \rightarrow (x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \cdots \rightarrow (x_{|S|}, y_{|S|})\) とします。ただし、\(|S|\) は文字列 \(S\) の長さです。
\(x_{|S|}, y_{|S|}\) をそれぞれ \(a, b\) とおきます。

\(1\) 回目の実行時にロボットが訪れるマス（ \(1\) 回目実行開始前の位置 \((0, 0)\) も含む）の集合を \(V_1\) とおきます。 つまり、\(V_1\) は \((0, 0), (x_1, y_1), (x_2, y_2), \cdots, (x_{|S|}, y_{|S|})\) から重複を除いて得られる集合です。 \(V_1\) の要素に適当に番号づけをし、

\(V_1 = \lbrace (X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N) \rbrace\)

と表します。ただし、\(N\) は \(V_1\) の要素数です。
このとき、\(2\) 回目の実行時にロボットが訪れるマス（ \(2\) 回目実行開始前の位置も含む）の集合 \(V_2\) は、\(V_1\) の各要素を \((a, b)\) だけ平行移動した、

\(V_2 = \lbrace (X_1 + a, Y_1 + b), (X_2 + a, Y_2 + b), \ldots, (X_N + a, Y_N + b) \rbrace\)

となります。
\(3\) 回目の実行時にロボットが訪れるマス（ \(3\) 回目実行開始前の位置も含む）の集合 \(V_3\) は、\(V_2\) の各要素をさらに \((a, b)\) だけ平行移動した、

\(V_3 = \lbrace (X_1 + 2a, Y_1 + 2b), (X_2 + 2a, Y_2 + 2b), \ldots, (X_N + 2a, Y_N+ 2b) \rbrace\)

となります。
一般に、\(k\) 回目の実行時にロボットが訪れるマス（ \(k\) 回目実行開始前の位置も含む）の集合 \(V_k\) は、

\(V_k = \lbrace (X_1 + (k-1)a, Y_1 + (k-1)b), (X_2 + (k-1)a, Y_2 + (k-1)b), \ldots, (X_N + (k-1)a, Y_N+ (k-1)b) \rbrace\)

となります。

特に、\(i = 1, 2, \ldots, N\) について \((X_i, Y_i) \in V_1\) は、

• \(2\) 回目の実行では \((X_i + a, Y_i + b)\) に対応し、
• \(3\) 回目の実行では \((X_i + 2a, Y_i + 2b)\) に対応し、
• \(\cdots\)
• \(k\) 回目の実行では \((X_i + (k-1)a, Y_i + (k-1)b)\) に対応する

ということに注意します。

ここで、\(i = 1, 2, \ldots, N\) に対して、

\(d_i\) := （\((X_i+ja, Y_i+jb) \in V_1\) を満たす最小の正整数 \(j\)）

と定めます。ただし、そのような正整数 \(j\) が存在しないときは \(d_i := \infty\) とします。

このとき、ある一つの \((X_i, Y_i) \in V_1\) に注目すると、\(d_i\) 回目の実行までは、

• マス \((X_i, Y_i)\) は、\(1\) 回目の実行時に初めて訪れるマスである。
• マス \((X_i + a, Y_i + b)\) は、\(2\) 回目の実行時に初めて訪れるマスである。
• マス \((X_i + 2a, Y_i + 2b)\) は、\(3\) 回目の実行時に初めて訪れるマスである。
• \(\cdots\)
• マス \((X_i + (d_i-1)a, Y_i + (d_i-1)b)\) は、\(d_i\) 回目の実行時に初めて訪れるマスである。

となりますが、\((d_i+1)\) 回目以降の実行では、

• マス \((X_i + d_ia, Y_i + d_ib)\) は、\((d_i+1)\) 回目の実行時に訪れるが、初めて訪れるマスではない。
  （ \(d_i\) の定義より \((X_i + d_ia, Y_i + d_ib) \in V_1\) なので\(1\)回目の実行時に訪問済み）
• マス \((X_i + (d_i+1)a, Y_i + (d_i+1)b)\) は、\((d_i+2)\) 回目の実行時に訪れるが、初めて訪れるマスではない。
  （ \((X_i + (d_i+1)a, Y_i + (d_i+1)b) = ((X_i+d_ia) + a, (Y_i+d_ib) + b)\) なので \(2\) 回目の実行時に訪問済み）
• マス \((X_i + (d_i+2)a, Y_i + (d_i+2)b)\) は、\((d_i+3)\) 回目の実行時に訪れるが、初めて訪れるマスではない。
  （ \((X_i + (d_i+2)a, Y_i + (d_i+2)b) = ((X_i+d_ia) + 2a, (Y_i+d_ib) + 2b)\) なので \(3\) 回目の実行時に訪問済み）
• \(\cdots\)

となります。
よって、\(S\) を \(K\) 回実行する際に、この \((X_i, Y_i)\) によって未訪問のマスが訪問済みに変わる回数は \(\min(d_i, K)\) 回です。

したがって、本問題の答えは、

\(\displaystyle\sum_{i = 1}^N \min(d_i, K)\)

です。

以上から、本問題はすべての \(i = 1, 2, \ldots, N\) について、\(d_i\) の値を求めることに帰着されます。これを高速に行う方法を以下に述べます。

\(a = b = 0\) のときは、\(d_1 = d_2 = \cdots = d_N = 1\) と分かります。 また、\(a = 0, b \neq 0\) の場合は \(X\) 座標と \(Y\) 座標の役割を交換することで、\(a \neq 0\) の場合に帰着できるので、以下では \(a \neq 0\) を仮定します。

まず \(i = 1, 2, \ldots, N\) ごとに、

\(q_i = \left\lfloor \displaystyle\frac{X_i}{a} \right\rfloor\)

\(s_i = X_i - q_i a\)

\(t_i = Y_i - q_i b\)

を計算し、\(V_1\) の要素を \((s_i, t_i)\) ごとにグループに分けます。 （ \((s_i, t_i) = (s_j, t_j)\) のときかつそのときに限り、\((X_i, Y_i)\) と \((X_j, Y_j)\) が同じグループに属するようにグループ分けします。）

任意の \(1 \leq i, j \leq N\) ついて、

\((s_i, t_i) = (s_j, t_j) \Leftrightarrow (X_j, Y_j) = (X_i + (q_j-q_i)a, Y_i + (q_j-q_i)b)\)

が成り立つので、各グループ内で \(q_i\) によってソートすることで、「すべての \(i = 1, 2, \ldots, N\) について \(d_i\) の値を求める」ことが、\(\mathrm{O}(N\log N)\) 時間でできます。

以上より、この問題を \(\mathrm{O}(|S|\log|S|)\) 時間で解くことができます。