Bajtazar intends to furnish his new apartment. For this purpose, he went to one of the nearby BITKEA stores and bought furniture of $n$ types, specifically $c_i$ items of furniture of type $i$.

Assembling the first furniture item of type $i$ (including studying the instructions in the Bajto-Swedish language) will take him $a_i$ minutes. While assembling further items, Bajtazar will gain experience — assembling the second and each subsequent furniture item of type $i$ will take him $d_i$ minutes less than assembling the previous item of that type.

Bajtazar decided that he will assemble some number of furniture items today. For each value $m_i$, he would like to know the minimum time in which he can assemble some $m_i$ of the purchased furniture items.

Input

The first line of the input contains two integers $n$ and $k$ ($1 \le n, k \le 500$), denoting respectively the number of furniture types and the number of queried values $m_i$. In the $i$-th of the next $n$ lines there are three integers $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$), describing the $i$-th type of purchased furniture. In the $i$-th of the next $k$ lines there is an integer $m_i$ ($1 \le m_i \le 20,000$).

In tests worth 10% of the points, the condition $1 \le n \le 50$ holds.

In tests worth 50% of the points, the condition $1 \le m_i \le 3000$ holds.

In tests worth 70% of the points, at least one of the above conditions holds.

Output

Print $k$ lines; in the $i$-th of them, output the minimum number of minutes needed to assemble $m_i$ furniture items. You may assume that assembling some $m_i$ furniture items will always be possible.

Example

For the input:

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

the correct output is:

19
30
49
62
70
75