Maximum Matching in a Special Bipartite Graph

You are given a bipartite graph where the right part has exactly (m) nodes labeled from (0) to (m-1). The left part consists of several nodes. Each left node is associated with a parameter (a). Such a node is connected to every right node (j) for which there exists a natural number (x \in \mathbb{N}) satisfying [ a \times x \equiv j \pmod{m} ] In other words, the set of neighbors for a left node with parameter (a) is [ S(a)={a\times x \bmod m \mid x \in \mathbb{N}},. ] It is well known that if (d = \gcd(a, m)), then (S(a)) is exactly the set of multiples of (d) modulo (m), having size (\frac{m}{d}).

The input is given in an aggregated form. You are given two arrays of length (n): the array (a_i) and the array (c_i). This means that there are (c_i) left nodes whose parameter is (a_i) (all (a_i) are pairwise distinct). Your task is to compute the size of a maximum matching in the bipartite graph.

A matching in a graph is a set of edges without common vertices. In this problem, each right node can be matched with at most one left node, and each left node (even if there are several nodes with the same parameter) can be matched with at most one right node. The goal is to select edges such that the total number of matched pairs is maximized.

inputFormat

The input consists of three lines. The first line contains two integers (m) and (n) separated by a space. Here, (m) ((1 \le m \le \ldots)) is the number of right nodes, and (n) is the number of distinct left node parameters. The second line contains (n) distinct integers: (a_1, a_2, \dots, a_n). The third line contains (n) integers: (c_1, c_2, \dots, c_n), where (c_i) represents the count of left nodes with parameter (a_i).

outputFormat

Output a single integer: the size of the maximum matching in the bipartite graph.

sample

6 2
4 3
2 1

3