题目链接：http://acm.nbu.edu.cn/v1.0/Problems/Problem.php?pid=2417
题目大意：
已知有n个商品，第i个商品有Xi个，每个商品Yi元（0<i<=n）。
询问m次，第j次询问表示是否存在若干个商品的价值和为Kj。
0<n<=15,0<m<=100000
0<Xi<=1000,0<Yi<=1000
0<Kj<1000000
时间限制是10s
题目思路：
很容易可以判断出这是一道多重背包的题目，那么多重背包会超时吗？
我们来算算看。
多重背包的比较容易的写法，是转化为01背包，那么对于该题转化为01背包的复杂度为O( max(Kj) * sum(Xi) )
Kj最大为10^6，sum(Xi)最大为15*10^3，显然10s也是不够用的。
那么优化一下，采用二进制优化，复杂度为O( max(Kj) * sum( log(Xi) ) )
sum( log(Xi) )最大约为150（小于150），10s可解。
那么何为二进制优化呢？
首先要知道两种解多重背包的方法都是对商品进行拆分，
01方法就是拆成每种商品个1个，
而二进制则不然，而是拆成1、2、4、8、……，
假如有某类商品有18件，那么就拆成1、2、4、8、3，
为什么呢？
因为1、2、4、8、3任意组合进行加法可以得到1~18，
所以我们这样拆分该商品那么某商品被选择的所有可能条件都会出现。
代码：
#pragma comment(linker, "/STACK:102400000,102400000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<string>
using namespace std;
#define ll long long
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n))
#define clr_all(x,c) memset(x,c,sizeof(x))
#define IT iterator
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle l+r>>1
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define eps (1e-8)
#define PI 3.1415926535897932384626433832795
#define E 2.7182818284590452353602874713527
template <class T> T _min(T a,T b){return a<b? a:b;}
template <class T> T _max(T a,T b){return a>b? a:b;}
template <class T> T _abs(T a){return a>0? a:-a;}
template <class T> T _mod(T a,T m){return a<m? (a<0? (a%m+m)%m:a):a%m;}
template <class T> T _gcd(T a,T b){while(b){T t=b;b=a%b;a=t;}return a;}
template <class T> void _swap(T &a,T &b){T t=b;b=a;a=t;}
template <class T> void getmax(T &a,T b){a= a>b? a:b;}
template <class T> void getmin(T &a,T b){a= (a!=-1 && a<b)? a:b;}
int TS,cas=1;
const int M=100000+5;
int n,m;
int k[M],x[22],y[22],o;
bool dp[M*10];
void bag01(int val){
for(int i=o;i>=val;i--) if(dp[i-val]) dp[i]=1;
}
void bagAll(int val){
for(int i=val;i<=o;i++) if(dp[i-val]) dp[i]=1;
}
void bagMult(int p){
if(x[p]*y[p] >= o) bagAll(y[p]);
for(int i=1;i<x[p];i<<=1) bag01(i*y[p]),x[p]-=i;
if(x[p]) bag01(x[p]*y[p]);
}
void run(){
int i,j;
for(i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
o=0;
for(i=1;i<=m;i++){
scanf("%d",&k[i]);
o=_max(o,k[i]);
}
for(i=1;i<=o;i++) dp[i]=0;
dp[0]=1;
for(i=1;i<=n;i++) bagMult(i);
//for(i=1;i<=o;i++) printf("dp[%d] = %s\n",i,dp[i]? "true":"false");
for(i=1;i<=m;i++) printf("%s\n", dp[k[i]]? "YES":"NO");
}
void presof(){
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
presof();
//run();
while(~scanf("%d%d",&n,&m)) run();
//for(scanf("%d",&TS),cas=1;cas<=TS;cas++) run();
return 0;
}