Bajtazar zamierza urządzić swoje nowe mieszkanie. W tym celu udał się do jednego z pobliskich sklepów sieci BITKEA i zakupił meble $\pi$ typów, konkretnie $c_i$ sztuk mebla typu $i$.

Złożenie pierwszego mebla typu $i$ (wraz z przestudiowaniem instrukcji w języku bajtoszwedzkim) zajmie mu $a_i$ minut. Składając kolejne meble, Bajtazar będzie nabierał wprawy - złożenie drugiego i każdego kolejnego mebla typu $i$ zajmie mu o $d_i$ minut krócej niż złożenie poprzedniego mebla tego typu.

Bajtazar zdecydował, że jeszcze dziś złoży pewną liczbę mebli. Dla każdej z wartości $m_i$ chciałby wiedzieć, w jakim najkrótszym czasie może złożyć pewne $m_i$ spośród zakupionych mebli.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $n$ i $k$ ($1 \le n, k \le 500$) oznaczające odpowiednio liczbę typów mebli i liczbę wartości $m_i$. W $i$-tym z kolejnych $n$ wierszy znajdują się trzy liczby całkowite $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$), stanowiące opis $i$-tego typu zakupionych mebli. W $i$-tym z kolejnych $k$ wierszy znajduje się liczba całkowita $m_i$ ($1 \le m_i \le 20\ 000$).

W testach wartych 10% punktów zachodzi warunek $1 \le n \le 50$.

W testach wartych 50% punktów zachodzi warunek $1 \le m_i \le 3000$.

W testach wartych 70% punktów zachodzi co najmniej jeden z powyższych warunków.

Wyjście

Na wyjście należy wypisać $k$ wierszy; w $i$-tym z nich powinna znaleźć się minimalna liczba minut potrzebna do złożenia $m_i$ mebli. Można założyć, że złożenie pewnych $m_i$ mebli będzie zawsze możliwe.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

19
30
49
62
70
75