Lựa chọn giá trị tối ưu (THT B Vòng Sơ loại Toàn quốc 2026 - Lần 1)

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho hai mảng số nguyên \(A\) và \(B\), mỗi mảng gồm \(N\) phần tử, với điều kiện \(B_i \ge A_i\) với mọi \(1 \le i \le N\).

Tại mỗi vị trí \(i\), bạn phải chọn chính xác một trong hai giá trị:

Chọn \(A_i\) và không mất chi phí;
Hoặc chọn \(B_i\) và phải trả chi phí \(C\).

Giả sử với một giá trị \(C\) đã cho, ta đưa ra lựa chọn tại mỗi vị trí. Khi đó, giá trị của phương án được tính bằng:

Tổng các giá trị đã chọn,
Trừ đi tổng chi phí phải trả cho các vị trí chọn \(B_i\).

Nếu có \(k\) vị trí chọn \(B_i\), thì tổng chi phí là \(k \cdot C\).

Yêu cầu

Cho \(Q\) giá trị khác nhau của \(C\). Với mỗi giá trị \(C\), hãy tính giá trị lớn nhất có thể đạt được.

Input

Dòng đầu chứa hai số nguyên \(N, Q\) (\(1 \le N, Q \le 2 \cdot 10^5\)).
Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) (\(0 \le A_i \le 10^9\)).
Dòng thứ ba chứa \(N\) số nguyên \(B_1, B_2, \ldots, B_N\) (\(0 \le B_i \le 10^9\)).
Dòng thứ tư chứa \(Q\) số nguyên \(C_1, C_2, \ldots, C_Q\) (\(0 \le C_i \le 10^9\)).

Output

In ra \(Q\) dòng, mỗi dòng là giá trị lớn nhất tương ứng với một \(C\).

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(N, Q \le 2000\).
Subtask \(2\) (\(30\%\) số điểm): \(A_i, B_i, C_i \le 2000\).
Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc bổ sung.

Example

Test 1

Input

Output

18
13
11

Note

Ta xét lần lượt từng giá trị \(C\):

Với \(C = 1\):
- Vị trí 1: chọn \(B_1 = 8\) tốt hơn chọn \(A_1 = 5\), vì tăng thêm \(3\) và chỉ mất phí \(1\).
- Vị trí 2: chọn \(B_2 = 3\) tốt hơn chọn \(A_2 = 2\), vì tăng thêm \(1\) và mất phí \(1\).
- Vị trí 3: chọn \(B_3 = 10\) tốt hơn chọn \(A_3 = 4\), vì tăng thêm \(6\) và mất phí \(1\).
- Khi đó ta chọn cả ba giá trị trong mảng \(B\). Tổng nhận được là \(8 + 3 + 10 = 21\), tổng chi phí là \(3 \cdot 1 = 3\). Giá trị cuối cùng là \(21 - 3 = 18\).
Với \(C = 4\):
- Vị trí 1: chọn \(A_1 = 5\), vì nếu chọn \(B_1 = 8\) thì chỉ hơn \(3\) nhưng phải trả phí \(4\).
- Vị trí 2: chọn \(A_2 = 2\), vì \(B_2 = 3\) chỉ hơn \(1\).
- Vị trí 3: chọn \(B_3 = 10\), vì hơn \(6\) so với \(A_3 = 4\), lớn hơn chi phí \(4\).
- Tổng nhận được là \(5 + 2 + 10 = 17\), tổng chi phí là \(4\). Giá trị cuối cùng là \(17 - 4 = 13\).
Với \(C = 7\):
- Ở cả ba vị trí, phần tăng thêm khi chọn \(B_i\) đều không vượt quá chi phí \(7\).
- Vì vậy, tốt nhất là chọn toàn bộ \(A\). Tổng giá trị là \(5 + 2 + 4 = 11\).

Bình luận (1)

Tải bình luận...

Kỳ thi:

THT B Vòng Sơ loại Toàn quốc 2026 - Lần 1 (29 Tháng ba, 2026)