Bạn đang cầm yasuo. Có ~n~ con creep. Con creep thứ ~i~ đứng ở vị trí ~a_i~, bạn phải giết hết ~n~ con creep này. Đồng thời bạn cũng có ~m~ skin yasuo, skin thứ ~i~ có phạm vi tấn công là ~b_i~ và tốn ~c_i~ mana, mỗi lần tấn công chỉ tiêu diệt được 1 con creep. Biết rằng yasuo này bị què nên luôn ở vị trí 0.

Yêu cầu: Tìm cách tiêu diệt kẻ thù sao cho lượng mana tiêu thụ là ít nhất, nếu không thể tiêu diệt hết, hãy in ra "Bo da mat Le Thu".

Input

• Dòng đầu tiên là 2 số nguyên ~n~ và ~m~ ~(n, m \le 10^5)~
• Dòng thứ 2 là ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~
• ~m~ dòng tiếp theo mỗi dòng là ~2~ số nguyên ~b_i~ và ~c_i~ tương ứng với skin thứ ~i~ ~(1 \le b_i, c_i \le 10^9)~

Output

Yêu cầu của bài

Giới hạn

• ~40~% số điểm có giới hạn ~n, m \le 10^3~
• ~60~% số điểm không có giới hạn gì thêm

Ví dụ

Sample input

4 2
1 2 3 4 
5 5
3 1

Sample output

8

Giải thích ví dụ

Dùng skin thứ ~2~ ba lần để tiêu diệt con creep thứ ~1, 2, 3~, dùng skin thứ nhất ~1~ lần để tiêu diệt con creep thứ ~4~