채소

작은 N은 채소 창고의 관리자이며, 채소 판매 계획을 설계하는 책임을 맡고 있다.

창고에는 총 $n$종류의 채소가 보관되어 있다. 작은 N은 채소마다 특성을 고려해 합리적인 판매 계획을 세우고, 이익을 최대로 얻어야 한다.

채소를 팔면 다음과 같이 수입이 생긴다. $i$번째 채소를 한 단위 팔 때마다 $a_i$의 수입을 얻는다. 정책이 다양한 판매를 장려하므로, $i$번째 채소를 처음 판매할 때는 추가로 $s_i$의 수입을 더 얻는다.

운영을 시작할 때 채소 $i$의 재고는 $c_i$단위다. 채소는 빨리 상하며, 상한 채소는 팔 수 없다. 각 채소에는 신선도 값 $x_i$가 있고, 모든 채소가 상할 때까지 매일 끝에 채소 $i$가 $x_i$단위씩 상한다. 각 단위가 상하는 시점은 고정되어 있으며, 판매량에 따라 바뀌지 않는다.

형식으로 쓰면 다음과 같다. $d \times x_i \le c_i$를 만족하는 모든 양의 정수 $d$에 대해, $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$일 동안 판매한다면 얻을 수 있는 최대 이익을 묻는다.

첫 줄에 세 양의 정수 $n$, $m$, $k$가 주어진다. 각각 채소 종류의 수, 하루 판매 총량의 상한, 질의의 수다. 다음 $n$줄에는 채소마다 0 이상의 정수 네 개 $a_i$, $s_i$, $c_i$, $x_i$가 차례로 주어진다. 이어서 $k$줄에 각각 0 이상의 정수 $p_j$가 주어진다.

$k$줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답을 출력한다.

• $n \le 10^5$
• $m \le 10$
• $p_j \le 10^5$
• 모든 테스트 데이터에서 각 질의 집합의 $p_j$는 서로 다르다.
• 모든 테스트 데이터에서 $0\le s_i,x_i\le 10^9$이다.