Bajtazar 打算给他的新公寓添置家具。为此，他去了附近的一家 BITKEA 商店，买了 $n$ 种类型的家具，其中第 $i$ 种买了 $c_i$ 件。

组装第 $i$ 种家具的第一件（包括阅读 Bajto-瑞典语说明书）需要 $a_i$ 分钟。随着继续组装，Bajtazar 会积累经验——组装第二件及之后的每一件第 $i$ 种家具所需时间都会比同类型上一件少 $d_i$ 分钟。

Bajtazar 决定今天要组装若干件家具。对于每个询问值 $m_i$，他想知道组装已购买家具中的任意 $m_i$ 件所需的最短时间。

输入格式

输入第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 500$），分别表示家具类型数以及询问的 $m_i$ 个数。接下来 $n$ 行中，第 $i$ 行包含三个整数 $a_i, d_i, c_i$（$1 \le a_i, d_i, c_i \le 10^9$，$a_i > (c_i - 1)\cdot d_i$），描述第 $i$ 种购买的家具。再接下来 $k$ 行中，第 $i$ 行包含一个整数 $m_i$（$1 \le m_i \le 20{,}000$）。

在占 10% 分数的测试中，满足条件 $1 \le n \le 50$。

在占 50% 分数的测试中，满足条件 $1 \le m_i \le 3000$。

在占 70% 分数的测试中，上述条件至少有一个成立。

输出格式

输出 $k$ 行；第 $i$ 行输出组装 $m_i$ 件家具所需的最少分钟数。你可以假设组装任意 $m_i$ 件家具总是可行的。

样例数据

对于输入：

3 6
20 3 6
25 20 2
19 1 19
1
2
3
4
5
6

正确输出为：

19
30
49
62
70
75