[AdditionalFile2660.zip](file://AdditionalFile2660.zip?type=additional_file)

#2660. 「POI2007 R3」砝码 Weights

标签: 传统 | 时间限制: 1500 ms | 内存限制: 32 MiB |

题目描述

译自 POI 2007 Stage 3. Day 1「Odważniki」

你需要把尽可能多的砝码装进一些容器里，且每个容器有总重量限制。对于任意两个砝码，保证其中一个砝码的重量整除另一个砝码的重量。

输入格式

第一行两个整数 $n,m$（$1 \le n,m \le 100\ 000$），分别表示容器的数量和砝码的数量。

接下来一行 $n$ 个整数 $w_i (1 \le w_i \le 1\ 000\ 000\ 000)$，表示容器的总重量限制。

接下来一行 $m$ 个整数 $m_i (1 \le m_i \le 1\ 000\ 000\ 000)$，表示砝码的重量。

输出格式

输出最多可以装进容器里的砝码数。

样例

输入

2 4
13 9
4 12 2 4

输出

3

其中任意三个砝码都可以放进容器里，但四个不行。