题目描述

本题需解决 完全背包问题，具体要求如下：

现有 $n$ 种物品，第 $i$ 种物品的单个体积为 $v_i$、价值为 $c_i$。每种物品可选择任意多个（包括 $0$ 个）。

共 $q$ 次询问，每次询问给定背包容积 $V$，需满足以下条件：

1. 选出的物品体积和 恰好等于 $V$；
2. 在满足条件 1 的前提下，最大化选出物品的价值和。

对于每次询问，输出最大价值和；若不存在体积和恰好为 $V$ 的选法，输出 $-1$。

输入格式

• 第一行：两个整数 $n$ 和 $q$，分别表示物品种数和询问次数。
• 接下来 $n$ 行：每行两个整数 $v_i$ 和 $c_i$，描述第 $i$ 种物品的体积和价值。
• 接下来 $q$ 行：每行一个整数 $V$，表示本次询问的背包容积。

输出格式

对于每组询问，输出一行整数：

• 若存在合法选法，输出最大价值和；
• 若不存在，输出 $-1$。

样例

输入

2 2
6 10
8 15
100000000001
100000000002

输出

-1
187500000000

说明

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

数据范围与提示

• 所有数据：$1 \leq n \leq 50$，$1 \leq v_i \leq 10^5$，$1 \leq c_i \leq 10^6$，$1 \leq q \leq 10^5$，$10^{11} \leq V \leq 10^{12}$。