If \(g=\gcd(N,M) > 1\), then \((i \bmod M) \bmod g=(i \bmod N) \bmod g\), so the problem can be divided into \(g\) independent problems, so we assume \(\gcd(N,M)=1\).

Let \(S_k\) be the set of integers \(i\) with \(0\le i < K\) and \(k \equiv i \bmod N\). Then \(\displaystyle \sum_{i=0}^{K-1}\min (A_{i \bmod N},B_{i \bmod M})=\sum_{k=0}^{N-1}\sum_{i\in S_k} \min (A_k, B_{i\bmod M})\).

Here, since \(\displaystyle S_k=\left\lbrace k+cN \left| 0 \le c < \left\lceil\frac{K-k}{N} \right\rceil\right. \right\rbrace\), for \(B_i'=B_{Ni\bmod M}\) we have

\[\displaystyle \sum_{i\in S_k} \min (A_k, B_{i\bmod M})=\sum_{c=0}^{\left\lceil\frac{K-k}{N} \right\rceil -1} \min\left(A_k,B'_{\left(\frac{i}{N}+c\right) \bmod M}\right).\]

Generalizing this sum, we see that it is sufficient if we can answer answer the following type of query for the integer sequence \(B'\):

• Given integers \(L,R\), and \(x\), find \(\displaystyle \sum_{c=L}^{R-1} \min(x,B'_{c\bmod M})\).

We can boil down to \(R-L<M\). Moreover, if \(c\bmod M\) has a leap, we can divide the problem in two by \(\displaystyle \left\lfloor\frac{c}{M} \right\rfloor\), each simply asking for \(\displaystyle \sum_{c=L}^{R-1} \min(x,B'_c)\). This reduced subproblems can be solved in a total of \(O(Q(\log Q + \log M))\) time, where \(Q\) is the total number of queries, by sorting the queries in ascending order of \(x\) and using a Fenwick tree.

Since \(Q\) is no greater than \(2N\), the answers can be computed in a total of \(O(N(\log N + \log M) + M)\) time.

Thus, the problem can be solved by implementing the algorithm appropriately.