本题中，你需要解决完全背包问题。

有 n 种物品，第 i 种物品单个体积为 v_i、价值为c_i。

q 次询问，每次给出背包的容积 V，你需要选择若干个物品，每种物品可以选择任意多个（也可以不选），在选出物品的体积的和恰好为 V 的前提下最大化选出物品的价值的和。你需要给出这个最大的价值和，或报告不存在体积和恰好为 V 的方案。

为了体现你解决 NP-Hard 问题的能力，V 会远大于 v_i，详见数据范围部分。

第一行两个整数 n,q，表示物品种数和询问次数。

接下来 n 行每行两个整数 v_i,c_i 描述一种物品。

接下来 q 行每行一个整数 V 描述一次询问中背包的体积。

对于每组询问输出一行一个整数。若不存在体积和恰好为 V 的方案，输出 -1；否则输出最大的选出物品的价值和。

第二组询问的最优方案为：选择 3 个物品 1 和 12499999998 个物品 2。

对于所有测试数据，1 \le n \le 50, 1 \le v_i \le 10^5, 1 \le c_i \le 10^6, 1 \le q \le 10^5, 10^{11} \le V \le 10^{12}。

THUPC