Bạn có \(N\) lá bài. Trên lá bài thứ \(i\), một số nguyên \(A_i\) được viết.

Với mỗi \(j = 1, 2, ..., M\) theo thứ tự này, bạn sẽ thực hiện phép toán sau một lần:

Phép toán: Chọn nhiều nhất \(B_j\) lá bài (có thể là không chọn lá nào). Thay thế số nguyên viết trên mỗi lá bài được chọn bằng \(C_j\).

Tìm tổng lớn nhất có thể của các số nguyên viết trên \(N\) lá bài sau \(M\) phép toán.

Ràng buộc

• Tất cả các giá trị đầu vào là số nguyên.
• \(1 \leq N \leq 10^5\)
• \(1 \leq M \leq 10^5\)
• \(1 \leq A_i, C_i \leq 10^9\)
• \(1 \leq B_i \leq N\)

INPUT FORMAT

Đầu vào được cung cấp từ Standard Input theo định dạng sau:

N
M
A_1 A_2 ... A_N
B_1 C_1
B_2 C_2
...
B_M C_M

OUTPUT FORMAT

In ra tổng lớn nhất có thể của các số nguyên viết trên \(N\) lá bài sau \(M\) phép toán.

Ví dụ:

Input

3 2
5 1 4
2 3
1 5

Output

14

Bằng cách thay thế số nguyên trên lá bài thứ hai bằng \(5\), tổng các số nguyên viết trên ba lá bài trở thành \(5 + 5 + 4 = 14\), đây là kết quả tối đa.

Input

10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4

Output

338

Giải thích ví dụ mẫu

Ví dụ 1:

• Input:

  3 2 5 1 4 2 3 1 5

• Giải thích:

  • Thay thế lá bài thứ hai (1) bằng 5, tổng sẽ là 5 + 5 + 4 = 14, đạt giá trị tối đa.

Ví dụ 2:

• Input:

  10 3 1 8 5 7 100 4 52 33 13 5 3 10 4 30 1 4

• Giải thích:

  • Tối ưu thay thế 3 lá đầu tiên bằng 10, 30, 4 để có tổng lớn nhất là 338.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House