P3462 [POI 2007] ODW-Weights

在搬迁到一个新的园区时，Byteotian 实验物理研究所遇到了一个后勤问题——转移其庞大的精密砝码收藏变得不那么简单。 研究所有若干个强度有限的容器可供使用。需要尽可能多地将砝码放入容器中，剩下的将被丢弃。除了不超过容器的强度外，放入容器中的砝码数量没有限制。一个容器也可以是空的。 研究所的任意两个砝码有一个特殊的性质：其中一个的质量是另一个质量的整数倍。特别地，它们可能具有相同的质量。 任务编写一个程序： 从标准输入中读取容器的强度和砝码的质量，确定可以放入容器中的最大砝码数量，将结果写入标准输出。

标准输入的第一行包含两个整数 $n$ 和 $m$（$1\le n,m\le 100\ 000$），用单个空格分隔，分别表示容器的数量和砝码的数量。标准输入的第二行由 $n$ 个整数 $w_i$（$1\le w_i\le 1\ 000\ 000\ 000$，$1\le i\le n$）组成，用单个空格分隔，表示容器的强度（单位：毫克）。第三行有 $m$ 个整数 $m_j$（$1\le m_j\le 1\ 000\ 000\ 000$，$1\le j\le m$），用单个空格分隔，表示砝码的质量（单位：毫克）。

标准输出的第一行应包含一个整数——可以放入容器中的最大砝码数量，而不超过其强度。

（由 ChatGPT 4o 翻译）