小 N — заведующий овощным складом, отвечающий за составление плана продажи овощей.

На складе хранится $n$ видов овощей. Учитывая свойства разных овощей и всевозможные факторы, 小 N должен составить разумный план продаж, приносящий наибольший доход.

При продаже каждой единицы овощей вида $i$ получается доход $a_i$.

Кроме того, поскольку государственная политика поощряет разнообразие продаваемых товаров, при первой продаже овощей вида $i$ получается дополнительный доход $s_i$.

В начале торговли на складе имеется $c_i$ единиц овощей вида $i$.

Однако срок хранения овощей весьма ограничен: испортившиеся овощи продавать нельзя. Сообразительный 小 N уже вычислил время порчи каждой единицы овощей. Для овощей вида $i$ задан параметр хранения $x_i$: в конце каждого дня портится $x_i$ единиц овощей, пока не испортятся все овощи. (Обратите внимание: время порчи каждой единицы овощей фиксировано и не меняется в зависимости от продаж.)

Формально: для каждого положительного целого $d$, удовлетворяющего $d\times x_i\le c_i$, в конце дня $d$ испортится $x_i$ единиц овощей.

В частности, если $(d-1)\times x_i\le c_i<d\times x_i$, то в конце дня $d$ испортится $c_i-(d-1)\times x_i$ единиц овощей.

Обратите внимание: $x_i=0$ означает, что овощи этого вида не портятся.

При этом общее количество овощей, продаваемых за день, ограничено и не может превышать $m$ единиц.

У 小 N есть $k$ вопросов, с которыми он просит вас помочь. Каждый вопрос имеет следующий вид: для заданного $p_j$, если продавать овощи в течение $p_j$ дней, каков максимально возможный доход?

Входные данные

Данные считываются из файла vegetables.in.

Первая строка содержит три положительных целых числа $n,m,k$: количество видов овощей, максимально допустимое суммарное количество продаваемых за день овощей и количество вопросов 小 N соответственно.

В следующих $n$ строках вводятся по четыре неотрицательных целых числа, описывающих свойства одного вида овощей: $a_i,s_i,c_i,x_i$ в указанном порядке. Их смысл описан выше.

В следующих $k$ строках вводится по одному неотрицательному целому числу $p_j$, смысл которого описан выше.

Выходные данные

Выведите результат в файл vegetables.out.

Выведите $k$ строк, содержащих по одному целому числу. Число в строке $i$ должно быть ответом на вопрос $i$.

Примеры

Входные данные 1

2 3 2
3 3 3 3
2 5 8 3
1
3

Выходные данные 1

16
27

Пример 2

См. файлы vegetables/vegetables2.in и vegetables/vegetables2.ans в каталоге участника.

Пример 3

См. файлы vegetables/vegetables3.in и vegetables/vegetables3.ans в каталоге участника.

Примечание к примеру 1

Есть два вида овощей:

При продаже овощей первого вида каждая единица приносит доход $3$, а первая продажа этого вида дополнительно приносит $3$. Всего есть $3$ единицы этих овощей, и все они испортятся в конце первого дня.

При продаже овощей второго вида каждая единица приносит доход $2$, а первая продажа этого вида дополнительно приносит $5$. Всего есть $8$ единиц этих овощей: $3$ испортятся в конце первого дня, $3$ — в конце второго, а $2$ — в конце третьего.

Если продавать овощи только $1$ день, следует продать $2$ единицы овощей первого вида и $1$ единицу овощей второго вида.

В этом случае доход от овощей первого вида равен $2\times3+3$, от овощей второго вида — $1\times2+5$, а суммарный доход равен $(2\times3+3)+(1\times2+5)=16$.

Если продавать овощи только $3$ дня, в первый день следует продать $3$ единицы овощей первого вида, во второй — $3$ единицы овощей второго вида (при этом нужно выбрать те $3$ единицы, которые испортятся в конце второго дня), а в третий — $2$ единицы овощей второго вида.

В этом случае доход от овощей первого вида равен $3\times3+3$, от овощей второго вида — $(3+2)\times2+5$, а суммарный доход равен $(3\times3+3)+[(3+2)\times2+5]=27$.

Подзадачи

Свойство 1: все $s_i$ равны $0$.

Свойство 2: все $x_i$ равны $0$.

Во всех тестах гарантируется, что значения $p_j$ во всех $k$ запросах попарно различны.

Во всех тестах гарантируется, что $0<a_i,c_i\le10^9$ и $0\le s_i,x_i\le10^9$.