小 N zarządza magazynem warzyw i odpowiada za opracowanie planu ich sprzedaży.

W magazynie znajduje się $n$ rodzajów warzyw. 小 N musi uwzględnić właściwości poszczególnych rodzajów i wszystkie istotne czynniki, aby opracować rozsądny plan sprzedaży przynoszący największy przychód.

Sprzedaż każdej jednostki warzyw rodzaju $i$ przynosi przychód $a_i$.

Ponadto, ponieważ polityka handlowa zachęca sprzedawców do różnorodności oferty, pierwsza sprzedaż warzyw rodzaju $i$ przynosi dodatkowy przychód $s_i$.

Na początku działalności zapas warzyw rodzaju $i$ wynosi $c_i$ jednostek.

Czas świeżości warzyw jest jednak bardzo ograniczony. Gdy się zepsują, nie można ich sprzedać. Sprytny 小 N obliczył już moment zepsucia każdej jednostki: dla warzyw rodzaju $i$ istnieje wartość świeżości $x_i$ i na koniec każdego dnia psuje się $x_i$ jednostek, aż wszystkie się zepsują. (Uwaga: moment zepsucia każdej jednostki jest ustalony i nie zmienia się wskutek sprzedaży).

Formalnie: dla każdej dodatniej liczby całkowitej $d$ spełniającej $d \times x_i \le c_i$, na koniec dnia $d$ psuje się $x_i$ jednostek warzyw.

W szczególności, jeśli $(d-1) \times x_i \le c_i < d \times x_i$, na koniec dnia $d$ psuje się $c_i - (d-1) \times x_i$ jednostek warzyw.

Zauważ, że $x_i = 0$ oznacza, iż warzywa tego rodzaju nigdy się nie psują.

Łączna liczba jednostek warzyw sprzedawanych każdego dnia jest ograniczona i nie może przekroczyć $m$.

小 N ma teraz $k$ pytań, w których obliczeniu prosi cię o pomoc. Każde ma postać: dla znanego $p_j$, jaki największy przychód można osiągnąć, jeśli sprzedaż ma trwać $p_j$ dni?

Wejście

Dane należy odczytać z pliku vegetables.in.

Pierwszy wiersz zawiera trzy dodatnie liczby całkowite $n, m, k$, oznaczające odpowiednio liczbę rodzajów warzyw, górne ograniczenie łącznej liczby jednostek sprzedawanych dziennie oraz liczbę pytań zadanych przez 小 N.

Każdy z następnych $n$ wierszy zawiera cztery nieujemne liczby całkowite opisujące właściwości jednego rodzaju warzyw: kolejno $a_i, s_i, c_i, x_i$, o znaczeniu opisanym powyżej.

Każdy z następnych $k$ wierszy zawiera jedną nieujemną liczbę całkowitą $p_j$, o znaczeniu opisanym powyżej.

Wyjście

Wynik należy zapisać do pliku vegetables.out.

Wypisz $k$ wierszy, każdy z jedną liczbą całkowitą. Liczba w wierszu $i$ oznacza odpowiedź na pytanie $i$.

Przykład

Wejście 1

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

Wyjście 1

16
27

Przykład 2

Zobacz pliki vegetables/vegetables2.in i vegetables/vegetables2.ans w katalogu zawodnika.

Przykład 3

Zobacz pliki vegetables/vegetables3.in i vegetables/vegetables3.ans w katalogu zawodnika.

Uwagi

Są dwa rodzaje warzyw:

Sprzedaż każdej jednostki pierwszego rodzaju przynosi przychód $3$, a pierwsza sprzedaż tego rodzaju daje dodatkowo $3$. Dostępne są 3 jednostki i wszystkie psują się na koniec pierwszego dnia.

Sprzedaż każdej jednostki drugiego rodzaju przynosi przychód $2$, a pierwsza sprzedaż tego rodzaju daje dodatkowo $5$. Dostępnych jest 8 jednostek: 3 psują się na koniec pierwszego dnia, 3 na koniec drugiego, a 2 na koniec trzeciego.

Przy sprzedaży trwającej tylko 1 dzień należy sprzedać 2 jednostki pierwszego rodzaju oraz 1 jednostkę drugiego rodzaju.

Wtedy przychód ze sprzedaży pierwszego rodzaju wynosi $2 \times 3 + 3$, ze sprzedaży drugiego rodzaju $1 \times 2 + 5$, a łączny przychód wynosi $(2 \times 3 + 3) + (1 \times 2 + 5) = 16$.

Przy sprzedaży trwającej tylko 3 dni należy pierwszego dnia sprzedać 3 jednostki pierwszego rodzaju, drugiego dnia 3 jednostki drugiego rodzaju (wybierając te 3 jednostki, które psują się na koniec drugiego dnia), a trzeciego dnia 2 jednostki drugiego rodzaju.

Wtedy przychód ze sprzedaży pierwszego rodzaju wynosi $3 \times 3 + 3$, ze sprzedaży drugiego rodzaju $(3+2) \times 2 + 5$, a łączny przychód wynosi $(3 \times 3 + 3) + [(3+2) \times 2 + 5] = 27$.

Podzadania

Właściwość 1: wszystkie $s_i$ są równe $0$.

Właściwość 2: wszystkie $x_i$ są równe $0$.

Dla wszystkich danych testowych zagwarantowano, że wartości $p_j$ w $k$ pytaniach są parami różne.

Dla wszystkich danych testowych zagwarantowano $0 < a_i, c_i \le 10^9$ oraz $0 \le s_i, x_i \le 10^9$.