Nhà ông \(T\) có nuôi \(n\) con mèo, con mèo thứ \(i\) hiện tại đang ở vị trí \(x_i\), vì có dự báo sắp có bão đổ bộ, nên ông tìm cách đưa các con mèo vào \(1\) nơi an toàn. May mắn thay, nhà ông có \(m\) lồng cho mèo, lồng thứ \(i\) có sức chứa \(b_i\) con mèo và được đặt tại vị trí \(a_i\). Ông muốn nhốt các con mèo của mình vào các lồng sao cho số lượng mèo ở \(1\) lồng bất kì không vượt quá sức chứa của lồng đấy đồng thời tổng độ mệt mỏi của \(n\) con mèo là ít nhất. (Độ mệt mỏi của \(1\) con mèo khi di chuyển từ vị trí \(x\) sang \(y\) là \(|x - y|\)). Vì không giỏi tính toán, nên bạn hãy tính độ mệt mỏi nhỏ nhất giúp ông \(T\) nhé.
NOTE : Các con mèo khác nhau sẽ ở vị trí khác nhau, các lồng khác nhau sẽ ở vị trí khác nhau

Input

• Dòng đầu tiên ghi \(2\) số \(n\) và \(m\) \((1 \le n, m \le 5*10^3)\) lần lượt là số mèo và số lồng;
• Dòng tiếp theo gồm \(n\) số nguyên phân biệt mô tả mảng \(x\) \((1 \le x_i \le 10^9)\) là vị trí của từng con mèo.
• \(m\) dòng tiếp theo, dòng thứ \(i\) gồm \(2\) số nguyên \(a_i\) và \(b_i\) lần lượt là vị trí và sức chứa của lồng thứ \(i\) (\(1 \le a_i \le 10^9\), \(0 \le b_i \le n\)).

Output

• Gồm \(1\) số nguyên tổng độ mệt mỏi bé nhất của \(n\) con mèo (Nếu không có cách chia thỏa mãn thì in ra \(-1\)).

Scoring

• Subtask \(1\) (\(30\%\) số điểm):\(0 \le b_i \le 1\) (với mọi \(i\) từ \(1\) đến \(m\)).
• Subtask \(2\) (\(70\%\) số điểm): Không có rằng buộc gì thêm.

3 5
1 4 7
3 1
5 1 
2 2
7 3
9 3

2