#P1427. Unequalled Consumption

    ID: 438 传统题 1000ms 512MiB 尝试: 49 已通过: 15 难度: 8 上传者: 标签>CF2400提高+/省选-最小公倍数多重背包计数 DP滑动窗口插板法二分答案

Unequalled Consumption

题目描述

对于方程 ∑i=1nwiti=S\sum_{i=1}^nw_it_i=S 这个方程,设其有不少于 pp 组解。

现在给出 n,p,w1⋯nn,p,w_{1\cdots n},请输出最小的 SS。

注意 t1⋯nt_{1\cdots n} 均为非负整数。

输入格式

第一行给出数字 nn。

第二行 nn 个数,代表 w1⋯nw_{1\cdots n}。

第三行一个数字 mm,代表有 mm 个询问。

第四行 mm 个数,每个数字代表一个 pp。

输出格式

mm 行,每行一个数 SS,对应于相应的 pp。

3
1 1 2
3
2 3 6
1
2
3

数据规模与约定

对于 100%100\% 的数据,1≤n≤51\leq n\leq 5,1≤wi,m≤101\leq w_i,m\leq 10,1≤p,S≤10181\leq p,S\leq 10^{18}。