只需要对John的付款数做一次多重背包，对shopkeeper的找零钱数做一次完全背包即可。

最重要的是上界的处理。可以注意到，John的付款数最多为maxv*maxv+m，也就是24400元。同理，shopkeeper找钱最多的数目为maxv*maxv.

证明如下：

如果John的付款数大于了maxv*maxv+m，即付硬币的数目大于了maxv，根据鸽笼原理，至少有两个的和对maxv取模的值相等，也就是说，这部分硬币能够用更少的maxv来代替。证毕。

转自：

另：Discuss里的数据不要信。。。。。

// by SiriusRen#include 
     
      #include 
      
       #include 
       
        using namespace std;int n,t,v[105],c[105],num[25000],f[25000],g[25000],ans=0x3ffffff;int main(){    scanf("%d%d",&n,&t);    for(int i=1;i<=n;i++)scanf("%d",&v[i]);    for(int i=1;i<=n;i++)scanf("%d",&c[i]);    memset(f,0x3f,sizeof(f)),f[0]=0;    memset(g,0x3f,sizeof(g)),g[0]=0;    for(int i=1;i<=n;i++){        memset(num,0,sizeof(num));        for(int j=0;j<=24500;j++)            if(f[j+v[i]]>f[j]+1&&num[j]