ly 在战场凹分，没吃午饭，饥肠辘辘的他从文具盒里翻出了一袋饼干...... 这袋饼干有 n 块，分别称作第 1,2...n 块，第 i 块饼干能提供 w [i] 的饱腹感. 有强迫症的 ly 必须从第 1 块开始吃，然后第 2 块... 直到总饱腹感达到（大于或等于）s 时即停止. 众所周知，万事万物都会随着多种因素的变化而变化，当然 ly 的饱腹感上限 s 也不例外 于是 ly 会询问你 q 次：当他的饱腹感上限为 s [i] 时，他需要吃多少块饼干 输入描述 对于每个测试点，有三行输入 第一行，输入两个正整数 n, q (n, q <= 20'0000),n 表示饼干的数量，q 表示询问的次数. 第二行，输入 n 个正整数 w [i]，(w [i] <= 1000) 表示第 i 块饼干的饱腹感. 第三行，输入 p 个正整数 s [i], (s [i] <= 2'0000'0000), 表示 ly 第 i 次询问时的饱腹感上限. 输出描述 仅一行：q 个正整数，第 i 个数表示 ly 第 i 次询问时需要吃的饼干数.

这是一个典型的背包问题，可以使用动态规划来解决。具体步骤如下：

1. 定义状态：设 dp[i][j] 表示前 i 块饼干中选择若干块，能否凑出 j 的饱腹感。

2. 状态转移方程：对于第 i 块饼干，有两种选择：选择或不选择。如果选择第 i 块饼干，则有 dp[i][j] = dp[i-1][j-w[i]]，即前 i-1 块饼干中选择若干块凑出 j-w[i] 的饱腹感，再加上第 i 块饼干的饱腹感 w[i]。如果不选择第 i 块饼干，则有 dp[i][j] = dp[i-1][j]。

3. 边界条件：dp[0][0] = true，其他 dp[0][j] = false。

4. 最终答案：对于每个询问，从后往前遍历 dp[n][s[i]], 找到最大的 j 使得 dp[n][j] = true，即可得到需要吃的饼干数。

代码如下：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 200005, MAXQ = 200005;

int n, q;
int w[MAXN], s[MAXQ];
bool dp[MAXN][MAXN];

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    memset(dp, false, sizeof(dp));
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < MAXN; j++) {
            if (j >= w[i]) {
                dp[i][j] = dp[i-1][j-w[i]];
            }
            dp[i][j] |= dp[i-1][j];
        }
    }
    for (int i = 1; i <= q; i++) {
        cin >> s[i];
        int j = s[i];
        while (!dp[n][j]) {
            j--;
        }
        cout << j << endl;
    }
    return 0;
}