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\) 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 "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

4 2
1 2 3 4 
5 5
3 1

8

4 1
1 2 3 10 
9 1

bin9638 da mat Nezuko