← 返回题目列表

Codeforces · 309/C

C. 数组内存

中文机器翻译题面 查看原题

您开始工作并打开计算机。您开始编码时很少考虑 RAM 在整个过程中的作用。在这个问题中,您的任务是解决您在计算机例程中遇到的问题之一。

我们将 RAM 视为可以包含数据的单元序列。有些单元格已经包含一些数据,有些单元格是空的。空细胞形成所谓的记忆簇。因此,存储器簇是一些连续的空存储器单元的序列。

你正好有n个记忆簇,第i个簇由ai个单元组成。您需要在程序中找到 m 个数组的内存。第 j 个数组占用 2bj 个连续的存储单元。可能没有足够的内存容纳所有 m 个数组,因此您的任务是确定可用内存簇中可以定位的数组的最大数量。当然,阵列不能在存储器簇之间划分。此外,任何单元格都不能属于两个数组。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 106)。下一行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。下一行包含 m 个整数 b1, b2, ..., bm (1 ≤ 2bi ≤ 109)。

输出

打印一个整数——问题的答案。

示例

输入 #1

5 3
8 4 3 2 2
3 2 2

输出 #1

2

输入 #2

10 6
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0

输出 #2

6

注意

在第一个示例中,给定大小为 8, 4, 3, 2, 2 的内存簇和大小为 8, 4, 4 的数组。获得等于 2 的答案的方法有几种:您可以将大小为 8 的数组定位到大小为 8 的簇,将其中一个大小为 4 的数组定位到大小为 4 的簇。另一种方法是将两个大小为 4 的数组定位到大小为 4 的簇。 8.

在第二个示例中,您将获得 10 个大小为 1 的内存簇和 6 个大小为 1 的数组。您可以选择任意 6 个簇并将所有给定数组定位到它们。