缺席的商人

小A是一个菜农，他每天都会带着自己种的 $V$ 份菜去交易市场置换金币。

已知交易市场总共有 $n$ 个固定的收购商人，每个商人都会有一个固定的报价，第 $i$ 个商人的报价是 $w_i$ 的金币收购 $v_i$ 份菜（商人不会在同一天重复收小A的菜）。

但是每一天都会有一个商人缺席，给你未来 $t$ 天商人的缺席情况，问小A未来 $t$ 天的每一天能够换回的最大金币数是多少？

输入格式

第一行，两个整数 $n,V$

接下来 $n$ 行，每行两个整数 $w_i,v_i$

接下来一行，一个整数 $t$

接下来 $t$ 行，每行一个整数 $x_i$ ，表示第 $i$ 天缺席的商人编号。

输出共 $t$ 行，每行一个整数，表示对应的那一天的最大金币收入是多少。

对于 $30\%$ 的数据，有 $1 \le n,t \le 15, 1 \le V \le 1000$

对于 $80\%$ 的数据，有 $1 \le n,t \le 100, 1 \le V \le 1000$

对于 $100\%$ 的数据，有 $1 \le n,t \le 2000, 1 \le V \le 5000$