Một xưởng sản xuất có \(M\) tổ đội công nhân, mỗi tổ phụ trách một nhóm công việc khác nhau. Hôm nay xưởng nhận được \(N\) đơn hàng, mỗi đơn hàng \(j\) thuộc nhóm \(g_j\) và mang lại lợi nhuận \(p_j\).

Tổ đội thứ \(i\) chỉ có thể xử lý tối đa \(k_i\) đơn hàng cùng lúc vì hạn chế về nhân sự và máy móc. Quản lý xưởng muốn chọn ra một tập các đơn hàng để nhận sao cho không vượt quá khả năng của từng tổ và tổng lợi nhuận là lớn nhất. Hãy giúp quản lý đưa ra quyết định nhé!

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \le M \le N \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(M\) số nguyên \(k_1, k_2, \dots, k_M\) (\(1 \le k_i \le N\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(g_j\) và \(p_j\) (\(1 \le g_j \le M\), \(1 \le p_j \le 10^9\)).

Kết quả ra

• In ra tổng lợi nhuận lớn nhất có thể đạt được.

Ví dụ

Input

6 3
2 1 2
1 10
1 8
2 15
3 5
3 12
1 7

Output

47

Subtask