Sử dụng Stand

Xem PDF

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

bin9638 là 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)\). bin9638 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. bin9638 luôn đứng cố định ở vị trí \(0\).

bin9638 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 bin9638 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\)\(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\)\(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 "bin9638 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 1
Output
8
Note

lúc đầu bin9638 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 1
Output
bin9638 da mat Nezuko
Note

không thể tiêu diệt kẻ địch ở vị trí 10.


Bình luận


  • 0
    huyhau6a2 8:57 p.m. 28 Tháng 12, 2021

    sau ngày đó, bin9638 đã khóc đến cuối đời do mất nezuko hmm ảo thật đấy


    • 0
      LeQuangMinh0903 5:05 p.m. 5 Tháng 11, 2021 chỉnh sửa 2

      một sự kết hợp ko hề nhẹ giữa naruto vs kimetsu no yaiba :))

      1 phản hồi

      • 1
        longkold00 10:06 p.m. 13 Tháng 10, 2021

        Nezuko là nữ 9 ngậm tre ấy hả :>