Phi thuyền và kho vàng

Điểm: 4,00 (OI)

Giới hạn thời gian: 4.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Assembly, C#, C++, D, Dart, Go, Groovy, Java, Javascript, Kotlin, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Ruby, Rust, Scratch, Typescript, Zig

Quân nổi dậy có $s$ phi thuyền, phi thuyền thứ $i$ có sức tấn công $a_{i}$ .

Đế chế có $b$ căn cứ, căn cứ thứ $j$ có sức phòng thủ $d_{j}$ và chứa $g_{j}$ đơn vị vàng.

Một phi thuyền có sức tấn công $a$ có thể tấn công mọi căn cứ có sức phòng thủ $d \leq a$ và lấy toàn bộ số vàng tại các căn cứ đó.

Với mỗi phi thuyền, hãy tính lượng vàng tối đa mà nó có thể lấy được (giả sử nó được phái đi một mình và các căn cứ chưa bị bất kỳ phi thuyền nào khác chạm tới).

Dữ liệu vào

Dòng đầu chứa hai số nguyên $s$ và $b$ .
Dòng thứ hai chứa $s$ số nguyên $a_{1}, a_{2}, \dots, a_{s}$ — sức tấn công của từng phi thuyền.
$b$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $d_{j}$ và $g_{j}$ — sức phòng thủ và lượng vàng của căn cứ thứ $j$ .

Dữ liệu ra

In ra $s$ số nguyên trên cùng một dòng, cách nhau bởi dấu cách, là lượng vàng tối đa mà mỗi phi thuyền lấy được, theo thứ tự xuất hiện trong dữ liệu vào.

Ràng buộc

$1 \leq s, b \leq 10^{5}$
$0 \leq a_{i} \leq 10^{9}$
$0 \leq d_{j} \leq 10^{9}$
$0 \leq g_{j} \leq 10^{4}$

Ví dụ

Input	Output	Giải thích
5 4 1 3 5 2 4 0 1 4 2 2 8 9 4	1 9 11 9 11	Phi thuyền 1 (sức tấn công 1) chỉ phá được căn cứ 1 (phòng thủ 0, vàng 1). Phi thuyền 2 (sức tấn công 3) phá được căn cứ 1 và 3 (phòng thủ 0 và 2), thu $1 + 8 = 9$ . Phi thuyền 3 (sức tấn công 5) phá được căn cứ 1, 2, 3, thu $1 + 2 + 8 = 11$ .
1 2 454169042 417874927 964 538969462 3466	964	Phi thuyền duy nhất có sức tấn công $4, 5 \times 10^{8}$ , chỉ vượt qua được căn cứ thứ nhất (phòng thủ $\approx 4, 17 \times 10^{8}$ ), lấy $964$ vàng.

Bình luận

Không có bình luận tại thời điểm này.