Problem: F: MOD Rush

problem

Given a positive integer sequence A of length N and a positive integer sequence B of length M.

For all (i, j) (1 \ leq i \ leq N, 1 \ leq j \ leq M), find the remainder of A_i divided by B_j and output the sum of them.

Input format


N M
A_1 A_2 ... A_N
B_1 B_2 ... B_M


Constraint

* 1 \ leq N, M \ leq 2 \ times 10 ^ 5
* 1 \ leq A_i, B_i \ leq 2 \ times 10 ^ 5
* All inputs are given as integers



Output format

Print the answer on one line. Please start a new line at the end.

Input example 1


3 3
5 1 6
2 3 4


Output example 1


9

* Consider the remainder of dividing the first element of sequence A by each element of sequence B. Dividing 5 by 2 gives too much 1, dividing by 3 gives too much 2, and dividing by 4 gives too much 1.
* Similarly, considering the second element, too much is 1, 1, 1, respectively.
* Considering the third element, too much is 0, 0, 2, respectively.
* If you add up too much, you get 1 + 2 + 1 + 1 + 1 + 1 + 0 + 0 + 2 = 9, so 9 is output.



Input example 2


twenty four
2 7
3 3 4 4


Output example 2


16

* The same value may be included more than once in the sequence, but the sum is calculated by calculating too much for each element.



Input example 3


3 1
12 15 21
3


Output example 3


0





Example

Input

3 3
5 1 6
2 3 4


Output

9

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

/* Starry Sky Tree */
//0-index

struct StarrySkyTree{
  typedef ll Type;
  int segn2;
  vector<pair<ll,int>> data;
  vector<Type> s_data;
  function<Type(Type, Type)> merge;

  StarrySkyTree(function<Type(Type, Type)> merge, int n): merge(merge)
  {
    for(segn2=1; segn2<n; segn2*=2);
    data.assign(segn2*2, {0, 0});
    s_data.assign(segn2*2, 0);
  }

  StarrySkyTree(int n):
    StarrySkyTree([](Type a, Type b){ return a + b; }, n) {}

  //get value of [a,b)
  pair<ll,int> query(int a, int b, int l = 0, int r = -1, int k = 0){
    if(r == -1) r = segn2;
    if(r <= a || b <= l) return {0, 0}; //大きさに注意
    if(a <= l && r <= b) return {data[k].first + data[k].second * s_data[k], data[k].second};

    auto p1 = query(a, b, l, (l+r)/2, k*2+1);
    auto p2 = query(a, b, (l+r)/2, r, k*2+2);

    int num = p1.second + p2.second;
    ll sum = p1.first + p2.first + num * s_data[k];

    return {sum, num};
  }

  //add x to [a,b)
  pair<ll,int> add(int a, int b, Type x, int l = 0, int r = -1, int k = 0){
    if(r == -1) r = segn2;
    if(a <= l && r <= b) {
      s_data[k] += x;
    } else if(a < r && l < b) {
      auto p1 = add(a, b, x, l, (l+r)/2, k*2+1);
      auto p2 = add(a, b, x, (l+r)/2, r, k*2+2);
      int num = p1.second + p2.second;
      ll sum = p1.first + p2.first;
      data[k] = {sum, num};
    }

    return {data[k].first + s_data[k] * data[k].second, data[k].second};
  }

  //add x to [a,b)
  pair<ll,int> add2(int a, int b, Type x, int l = 0, int r = -1, int k = 0){
    if(r == -1) r = segn2;
    if(a <= l && r <= b)
      data[k].second += x;
    else if(a < r && l < b) {
      auto p1 = add2(a, b, x, l, (l+r)/2, k*2+1);
      auto p2 = add2(a, b, x, (l+r)/2, r, k*2+2);
      int num = p1.second + p2.second;
      ll sum = p1.first + p2.first;
      data[k] = {sum, num};
    }

    return {data[k].first + s_data[k] * data[k].second, data[k].second};
  }

};

ll test(int N) {
  ll sum = 0;

  for (int i=1; i<=N; i++) {
    sum += N / i * 2;
  }

  return sum;
}

int counter[SIZE];
int B[SIZE];

int main(){
  int N, M;
  int L = 0;

  scanf("%d%d", &N, &M);

  for (int i=0; i<N; i++) {
    int a;
    scanf("%d", &a);
    counter[a]++;
    L = max(L, a+1);
  }

  B[0] = 1;
  M++;
  for (int i=1; i<M; i++) {
    scanf("%d", B+i);
  }

  sort(B, B+M);

  StarrySkyTree seg(L);

  ll ans = 0;

  for (int i=0; i<L; i++) {
    seg.add2(i, i+1, counter[i]);
  }

  for (int i=1; i<M; i++) {
    debug(i);
    if (B[i-1] != B[i]) {

      int a = B[i-1];
      int b = B[i];

      set<int> ss;

      for (ll j=0; j*a<L; j++)
        ss.insert(j * a);

      for (ll j=0; j*b<L; j++)
        ss.insert(j * b);

      ss.insert(L);


      int prev = -1;
      for (int t : ss) {
        if (prev >= 0) {
          int d = prev % b - prev % a;
          seg.add(prev, t, d);
        }
        prev = t;
      }
    }

    debug(B[i]);
    debug(seg.query(0, L));
    ans += seg.query(0, L).first;
  }

  cout << ans << endl;

  return 0;
}