Sử dụng Stand
Xem PDFlà trưởng dòng họ Joseph đồng thời là người sở hữu tất cả stand mạnh nhất thế giới như: The World, Platinum, Gold Experience Requiem, King Crimson,... Hôm nay anh có \(1\) trận chiến với kẻ địch của mình là Muzan Kibutsuji để giải cứu em gái anh là Nezuko. Để giải cứu Nezuko thì anh phải tiêu diệt \(n\) kẻ địch \((n≤10^5)\), kẻ địch thứ \(i (i ≤ n)\) đứng ở vị trí nguyên dương \(A_i (1≤ A_i ≤ 10^9)\). cũng đồng thời sở hữu \(m\) stand \((m ≤ 10^5 )\), stand thứ \(i(i ≤ m)\) có phạm vi tấn công là \(B_i\) và mức độ tiêu tốn chakra là \(C_i\) \((1≤ B_i, C_i ≤ 10^9)\). Mỗi lần tấn công stand thứ \(i\) sẽ có thể tiêu diệt \(1\) kẻ thù trong phạm vi \(B_i\) và tiêu tốn \(C_i\) chakra. luôn đứng cố định ở vị trí \(0\).
muốn tiêu diệt hết kẻ thù sao cho lượng chakra tiêu tốn là ít nhất, khổ nỗi cậu ấy không biết nên sử dụng stand thế nào cho hợp lí. Hãy giúp nhé !
Yêu cầu:
- tính lượng chakra tối thiểu để tiêu diệt kẻ địch.
Input:
- Dòng đầu tiên lần lượt là \(2\) số \(n\) và \(m\).
- Dòng thứ \(2\) là dãy \(A\).
- \(m\) dòng tiếp theo mỗi dòng gồm hai số là \(B_i\) và \(C_i\) tương ứng.
Output:
- \(1\) số duy nhất là kết quả, nếu không thể tiêu diệt hết kẻ địch thì in ra " da mat Nezuko".
Scoring
- Subtask \(1\) (\(40\%\) số điểm): \(n, m ≤ 10^3\).
- Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm.
Example
Test 1
Input
4 2
1 2 3 4
5 5
3 1Output
8Note
lúc đầu dùng stand thứ \(2\) để tiêu diệt kẻ thù ở vị trí \(1, 2, 3\) sau đó dùng stand thứ \(1\) để tiêu diệt kẻ thù ở vị trí \(4\).
Test 2
Input
4 1
1 2 3 10
9 1Output
bin9638 da mat NezukoNote
không thể tiêu diệt kẻ địch ở vị trí 10.
Bình luận
ủa test 1 dùng stand 1 là chỉ tốn 5 mà một phát hết luôn mà bạn ???
sau ngày đó, bin9638 đã khóc đến cuối đời do mất nezuko hmm ảo thật đấy
một sự kết hợp ko hề nhẹ giữa naruto vs kimetsu no yaiba :))
Nezuko là nữ 9 ngậm tre ấy hả :>