{"code":"lqdojcontest10bai5","name":"LQDOJ Contest #10 - Bài 5 - Mèo Và Mèo","description":"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é.\r\n**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\r\n\r\n#### Input\r\n - 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;\r\n - 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.\r\n - $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$).\r\n\r\n#### Output\r\n- 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$).\r\n\r\n#### Scoring\r\n- Subtask $1$ ($30\\%$ số điểm):$0 \\le b_i \\le 1$ (với mọi $i$ từ $1$ đến $m$).\r\n- Subtask $2$ ($70\\%$ số điểm): Không có rằng buộc gì thêm.\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 5\r\n        1 4 7\r\n        3 1\r\n        5 1 \r\n        2 2\r\n        7 3\r\n        9 3\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2\r\n        ```\r\n    ??? warning \"Note\"\r\n        Con mèo thứ nhất đi vào lồng thứ $3$\r\n        Con mèo thứ $2$ đi vào lồng thứ nhất\r\n        Con mèo thứ $3$ đi vào lồng thứ $4$","points":1500.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}