小N là người quản lý kho rau, chịu trách nhiệm thiết kế phương án bán rau.
Trong kho có tất cả $n$ loại rau. 小N cần dựa vào đặc điểm của từng loại rau, cân nhắc tổng hợp các yếu tố để thiết kế một phương án bán hợp lý nhằm thu được lợi nhuận lớn nhất.
Khi tính lợi nhuận bán rau, mỗi đơn vị rau loại $i$ bán được đem lại lợi nhuận $a_i$.
Đặc biệt, vì chính sách khuyến khích người bán đa dạng hóa mặt hàng, lần đầu bán rau loại $i$ còn đem lại một khoản lợi nhuận bổ sung $s_i$.
Khi bắt đầu kinh doanh, lượng tồn kho của rau loại $i$ là $c_i$ đơn vị.
Tuy nhiên, thời gian bảo quản rau rất hạn chế: một khi đã hỏng thì không thể bán nữa. Nhưng 小N thông minh đã tính được thời điểm hỏng của từng đơn vị rau: đối với rau loại $i$, tồn tại giá trị bảo quản $x_i$; cuối mỗi ngày có $x_i$ đơn vị rau bị hỏng cho đến khi toàn bộ rau đều hỏng. (Chú ý: thời điểm hỏng của mỗi đơn vị rau là cố định, không thay đổi theo việc bán rau.)
Một cách hình thức: với mọi số nguyên dương $d$ thỏa mãn $d\times x_i\le c_i$, có $x_i$ đơn vị rau sẽ hỏng vào cuối ngày thứ $d$.
Đặc biệt, nếu $(d-1)\times x_i\le c_i<d\times x_i$, thì có $c_i-(d-1)\times x_i$ đơn vị rau sẽ hỏng vào cuối ngày thứ $d$.
Chú ý rằng $x_i=0$ có nghĩa là loại rau này không bị hỏng.
Đồng thời, tổng lượng rau bán được mỗi ngày cũng có giới hạn, không được vượt quá $m$ đơn vị.
Bây giờ, 小N có $k$ câu hỏi và muốn nhờ bạn tính giúp. Mỗi câu hỏi có dạng: với $p_j$ đã biết, nếu cần bán trong $p_j$ ngày thì lợi nhuận lớn nhất có thể thu được là bao nhiêu?
Dữ liệu vào
Đọc dữ liệu từ tệp vegetables.in.
Dòng đầu tiên chứa ba số nguyên dương $n,m,k$, lần lượt biểu thị số loại rau, giới hạn trên của tổng lượng rau có thể bán trong mỗi ngày, và số câu hỏi của 小N.
Trong $n$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên không âm mô tả đặc điểm của một loại rau, theo thứ tự là $a_i,s_i,c_i,x_i$, với ý nghĩa như đã nêu ở trên.
Trong $k$ dòng tiếp theo, mỗi dòng chứa một số nguyên không âm $p_j$, với ý nghĩa như đã nêu ở trên.
Dữ liệu ra
Ghi kết quả vào tệp vegetables.out.
In $k$ dòng, mỗi dòng chứa một số nguyên; số ở dòng thứ $i$ là câu trả lời cho câu hỏi thứ $i$.
Ví dụ
Dữ liệu vào 1
2 3 2 3 3 3 3 2 5 8 3 1 3
Dữ liệu ra 1
16 27
Ví dụ 2
Xem các tệp vegetables/vegetables2.in và vegetables/vegetables2.ans trong thư mục của thí sinh.
Ví dụ 3
Xem các tệp vegetables/vegetables3.in và vegetables/vegetables3.ans trong thư mục của thí sinh.
Ghi chú
Có hai loại rau:
Khi bán rau loại $1$, mỗi đơn vị bán được đem lại lợi nhuận $3$, và lần đầu bán loại rau này còn đem lại lợi nhuận bổ sung $3$. Có tất cả $3$ đơn vị rau loại này, đều sẽ hỏng vào cuối ngày đầu tiên.
Khi bán rau loại $2$, mỗi đơn vị bán được đem lại lợi nhuận $2$, và lần đầu bán loại rau này còn đem lại lợi nhuận bổ sung $5$. Có tất cả $8$ đơn vị rau loại này, trong đó $3$ đơn vị hỏng vào cuối ngày đầu tiên, $3$ đơn vị hỏng vào cuối ngày thứ hai, và $2$ đơn vị hỏng vào cuối ngày thứ ba.
Nếu chỉ bán trong $1$ ngày thì nên bán $2$ đơn vị rau loại thứ nhất và $1$ đơn vị rau loại thứ hai.
Trong trường hợp này: lợi nhuận từ rau loại thứ nhất là $2\times 3+3$; lợi nhuận từ rau loại thứ hai là $1\times 2+5$; tổng lợi nhuận là $(2\times 3+3)+(1\times 2+5)=16$.
Nếu chỉ bán trong $3$ ngày thì ngày đầu nên bán $3$ đơn vị rau loại thứ nhất, ngày thứ hai nên bán $3$ đơn vị rau loại thứ hai (lúc này chọn bán $3$ đơn vị sẽ hỏng vào cuối ngày thứ hai), và ngày thứ ba bán $2$ đơn vị rau loại thứ hai.
Trong trường hợp này: lợi nhuận từ rau loại thứ nhất là $3\times 3+3$; lợi nhuận từ rau loại thứ hai là $(3+2)\times 2+5$; tổng lợi nhuận là $(3\times 3+3)+[(3+2)\times 2+5]=27$.
Nhiệm vụ con
| Số thứ tự bộ kiểm thử | $n$ | $m$ | $p_j$ | Đặc tính 1 | Đặc tính 2 |
|---|---|---|---|---|---|
| $1$ | $\le 2$ | $\le 10$ | $\le 10^3$ | Không | Không |
| $2$ | $\le 3$ | $\le 10$ | $\le 10^3$ | Không | Không |
| $3$ | $\le 4$ | $\le 10$ | $\le 10^3$ | Không | Không |
| $4$ | $\le 10^3$ | $\le 10$ | $\le 2$ | Không | Không |
| $5$ | $\le 10^3$ | $\le 10$ | $\le 3$ | Không | Không |
| $6$ | $\le 10^3$ | $\le 10$ | $\le 4$ | Không | Không |
| $7$ | $\le 4$ | $\le 1$ | $\le 4$ | Không | Không |
| $8$ | $\le 6$ | $\le 2$ | $\le 6$ | Không | Không |
| $9$ | $\le 8$ | $\le 1$ | $\le 8$ | Không | Không |
| $10$ | $\le 10$ | $\le 2$ | $\le 10$ | Không | Không |
| $11$ | $\le 20$ | $\le 3$ | $\le 20$ | Không | Không |
| $12$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Có | Không |
| $13$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Không | Có |
| $14$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Không | Không |
| $15$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Không | Không |
| $16$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Có | Có |
| $17$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Có | Không |
| $18$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Không | Có |
| $19$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Không | Không |
| $20$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Không | Không |
| $21$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Có | Có |
| $22$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Có | Không |
| $23$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Không | Có |
| $24$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Không | Không |
| $25$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Không | Không |
Đặc tính 1: tất cả $s_i$ đều bằng $0$.
Đặc tính 2: tất cả $x_i$ đều bằng $0$.
Với mọi dữ liệu kiểm thử, bảo đảm các giá trị $p_j$ trong $k$ truy vấn đôi một khác nhau.
Với mọi dữ liệu kiểm thử, bảo đảm $0<a_i,c_i\le 10^9$, $0\le s_i,x_i\le 10^9$.