高级的暴力，神仙优化……

首先$O(n^{3})$的$dp$很好想，然后这样可以$O(1)$地回答询问。

考虑到所有物品的体积是一个连续的区间，所以说我们可以合并一些物品来达到预处理时间均摊的效果。

我们知道$k = pm + q$表示一个带余除法，那么我们对于每一个$k$，考虑枚举物品的体积$v$然后选取一个适当的模数$m$来优化计算。

对于每一个询问$ans = max(f_{pm, i}, f_{q, v - i})   ( 0 \leq i \leq v)$

这样的话我们预处理$f_{0,1,2,...,m}$和$f_{m, 2m, 3m, ..., km}  (n \leq km)$就可以回答问题了。

根据分块的思想当$m = \sqrt{n}$时，合并后的物品的数量是根号级别的，这样预处理的时间复杂度是$O(n ^ {2.5})$较优，回答每一个询问的时间是$O(n)$，可以通过本题。

还有一个小细节就是要注意当$q$取1时其实答案只能取$f_{q, v}$，但是找答案的过程中可能会出现$f_{q, i} (i < v)$比答案大的情况，所以我们将$f$先全部标记为不合法状态，然后记$f_{0, 0} = 0$为合法状态，就可以避免中间项答案的干扰。

膜Claris。

Code：

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 1505;const int M = 45;const int inf = 1 << 30;int n, m, qn, w[N], f[M][N], g[M][N];inline void read(int &X) {    X = 0;    char ch = 0;    int op = 1;    for(; ch > '9'|| ch < '0'; ch = getchar())        if(ch == '-') op = -1;    for(; ch >= '0' && ch <= '9'; ch = getchar())        X = (X << 3) + (X << 1) + ch - 48;    X *= op;}inline void chkMax(int &x, int y) {    if(y > x) x = y;}int main() {    memset(f, 128, sizeof(f));    memset(g, 128, sizeof(g));           read(n), read(qn);    m = sqrt(n) + 1;    for(int i = 0; i <= n; i++) {        read(w[i]);        f[1][i] = w[i];    }        for(int i = 2; i <= m; i++)        for(int j = 0; j <= n; j++)            for(int k = 0; k <= j; k++)                chkMax(f[i][j], f[i - 1][k] + w[j - k]);        g[0][0] = f[0][0] = 0;    for(int i = 0; i <= n; i++)         g[1][i] = f[m][i];            for(int i = 2; i <= m; i++)        for(int j = 0; j <= n; j++)            for(int k = 0; k <= j; k++)                chkMax(g[i][j], g[i - 1][k] + f[m][j - k]);        for(int k, v, a, b, ans; qn--; ) {        read(k), read(v);        ans = -inf, a = k / m, b = k % m;        for(int i = 0; i <= v; i++)            chkMax(ans, f[b][i] + g[a][v - i]);        printf("%d\n", ans);    }        return 0;}