P1003

[POI2007]砝码Odw

[POI2007]砝码Odw

Byteotian 公司在搬家时，需要运输大量精密砝码。公司拥有 nn 个容量固定的容器，并希望在不超过各容器容量的前提下，装入尽可能多的砝码；未能装入容器的砝码将被丢弃。

每个砝码至多放入一个容器，每个容器可以放入任意数量的砝码，也可以为空，但其中砝码的总质量不能超过该容器的容量。

这些砝码具有一个特殊性质：对于任意两个砝码，其中一个砝码的质量一定是另一个砝码质量的整数倍；两个砝码的质量也可能相等。

请计算最多能够装入容器的砝码数量。

输入格式

第一行包含两个整数 nn 和 mm，分别表示容器数量和砝码数量。

第二行包含 nn 个整数 wiw_i，其中 wiw_i 表示第 ii 个容器的容量。

第三行包含 mm 个整数 mjm_j，其中 mjm_j 表示第 jj 个砝码的质量。

输出格式

输出一个整数，表示最多能够装入容器的砝码数量。

样例输入

2 4
13 9
4 12 2 4

样例输出

3

数据范围

  • 1≤n,m≤1051\le n,m\le 10^5；
  • 1≤wi≤1091\le w_i\le 10^9；
  • 1≤mj≤1091\le m_j\le 10^9；
  • 对于任意两个砝码，其中一个砝码的质量是另一个砝码质量的整数倍。

来源与许可

本题为 POI 2007 试题「砝码」，题面与测试数据整理自 BZOJ。

样例 1

输入

2 4
13 9
4 12 2 4

输出

3