Description

农夫约翰打算建立一个栅栏将他的牧场给围起来, 因此他需要一些特定规格的木材. 于是农夫约翰到木材店购买木材. 可是木材店老板说他这里只剩下少部分大规格的木板了. 不过约翰可以购买这些木板, 然后切割成他所需要的规格. 而且约翰有一把神奇的锯子, 用它来锯 木板, 不会产生任何损失, 也就是说长度为 \(10\) 的木板可以切成长度为 \(8\) 和 \(2\) 的两 个木板. 你的任务是, 给你约翰所需要的木板的规格, 还有木材店老板能够给出的木材的规 格, 求约翰最多能够得到多少他所需要的木板.

Input

第一行为整数 \(m\) 表示木材店老板可以提供多少块木材给约翰. 紧跟着 \(m\) 行为老板提供 的每一块木板的长度. 接下来一行为整数 \(n\), 表示约翰需要多少木材. 接下来 \(n\) 行表示他所需要的每一块木板的长度. 木材的规格小于 \(32767\). (对于店老板提供的和约翰需要的每块木板, 你只能使用一次).

Output

只有一行, 为约翰最多能够得到的符合条件的木板的个数.

Sample Input

4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30

Sample Output

7

Data Range

对于所有数据, 满足:\(m \leq 50, n \leq 1000\)

Explanation

先把所有的对象从小到大排一遍序, 然后去掉根本不可能的元素.

这样一来就可以爆搜最开始的前面几块木板可不可以被切出来了, 二分答案加上爆搜可以 水过此题.

Source Code

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 1010;

int n, m;
lli a[maxn], b[maxn];
lli sum_a, sum_b[maxn];

bool flag = false;
lli bl[maxn];
void dfs(int pa, int pb, int len, int sum)
{
    // Final status.
    if (pb == 0)
        flag = true;
    // Skipping non-choosable boards
    while (pa <= n && a[pa] < b[1])
        sum += a[pa++];
    // That would be impossible.
    if (flag || pa > n)
        return ;
    if (sum + sum_b[len] > sum_a)
        return ;
    // Searching further situations.
    int t = pa, t1 = pa, t2 = pb, t3 = sum;
    if (b[pb] == b[pb + 1] && pb != len)
        t = bl[pb + 1];
    for (int i = t; i <= n; i++)
        // If selectable of this board
        if (a[i] >= b[pb]) {
            bl[pb] = i;
            a[i] -= b[pb--];
            dfs(pa, pb, len, sum);
            pa = t1;
            pb = t2;
            sum = t3;
            a[i] += b[pb];
        }
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
        scanf("%lld", &b[i]);
    // Arranging data sequences
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + m);
    // Removing boards that are too large to satisfy
    while (b[m] > a[n])
        m--;
    // Removing base-boards that are too small to be cut up
    int new_n = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] > b[1])
            a[++new_n] = a[i];
    n = new_n;
    // Calculating sums.
    for (int i = 1; i <= n; i++)
        sum_a += a[i];
    for (int i = 1; i <= m; i++)
        sum_b[i] = sum_b[i - 1] + b[i];
    // Binary searching results
    int l = 1, r = m, res = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        flag = false;
        dfs(1, mid, mid, 0);
        if (flag) l = mid + 1, res = mid;
        else r = mid - 1;
    }
    printf("%d\n", res);
    return 0;
}