F: MOD Rush
問題
長さ N の正の整数列 A と、長さ M の正の整数列 B が与えられます。
すべての (i, j) (1 \leq i \leq N, 1 \leq j \leq M) について、A_i を B_j で割ったあまりを求め、それらの和を出力してください。
入力形式
N M
A_1 A_2 ... A_N
B_1 B_2 ... B_M
制約
- 1 \leq N, M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 2 \times 10^5
- 入力はすべて整数で与えられる
出力形式
答えを 1 行に出力してください。最後に改行してください。
入力例 1
3 3
5 1 6
2 3 4
出力例 1
9
- 数列 A の 1 番目の要素を、数列 B の各要素で割ったあまりを考えます。5 を 2 で割るとあまりは 1、3 で割るとあまりは 2、4 で割るとあまりは 1 です。
- 同様に 2 番目の要素についても考えると、あまりはそれぞれ 1, 1, 1 です。
- 3 番目の要素についても考えると、あまりはそれぞれ 0, 0, 2 です。
- あまりを合計すると 1 + 2 + 1 + 1 + 1 + 1 + 0 + 0 + 2 = 9 となるので、9 を出力します。
入力例 2
2 4
2 7
3 3 4 4
出力例 2
16
- 数列内には同じ値が複数含まれていることがありますが、それぞれの要素に対してあまりを計算して和を求めます。
入力例 3
3 1
12 15 21
3
出力例 3
0