P1215

Pku1837 Balance

Pku1837 Balance

Gigel 有一架特殊的天平。天平由两条重量可忽略、长度均为 1515 的臂组成，臂上安装了若干挂钩。

天平共有 CC 个挂钩和 GG 个砝码。每个挂钩的位置由它相对于天平中心的横坐标表示：负数表示挂钩位于左臂，正数表示挂钩位于右臂，绝对值表示挂钩到天平中心的距离。

每个砝码都可以挂在任意一个挂钩上，同一个挂钩可以悬挂多个砝码，但必须使用全部 GG 个砝码。当所有砝码对天平中心产生的力矩之和为 00 时，天平达到平衡。

请计算共有多少种不同的砝码悬挂方案可以使天平平衡。保证每组测试数据都至少存在一种可行方案。

输入格式

第一行包含两个整数 CC 和 GG，分别表示挂钩数量和砝码数量。

第二行包含 CC 个互不相同的整数，依次表示各挂钩相对于天平中心的位置。

第三行包含 GG 个互不相同的正整数，依次表示各砝码的重量。

输出格式

输出一个整数 MM，表示能够使天平平衡的悬挂方案数。

样例输入

2 4
-2 3
3 4 5 8

样例输出

2

样例解释

一种方案是将重量为 44 和 88 的砝码挂在位置 −2-2 的挂钩上，将重量为 33 和 55 的砝码挂在位置 33 的挂钩上。

另一种方案是将重量为 33、44 和 55 的砝码挂在位置 −2-2 的挂钩上，将重量为 88 的砝码挂在位置 33 的挂钩上。

数据范围

  • 2≤C≤202\le C\le 20；
  • 2≤G≤202\le G\le 20；
  • 挂钩位置均为 [−15,15][-15,15] 范围内互不相同的整数；
  • 砝码重量均为 [1,25][1,25] 范围内互不相同的整数；
  • MM 是不超过 101510^{15} 的非负整数；
  • 保证至少存在一种使天平平衡的方案。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

2 4
-2 3
3 4 5 8

输出

2