English · Original
Chinese · Translation
Formal · Original
One day Masha came home and noticed _n_ mice in the corridor of her flat. Of course, she shouted loudly, so scared mice started to run to the holes in the corridor.
The corridor can be represeted as a numeric axis with _n_ mice and _m_ holes on it. _i_th mouse is at the coordinate _x__i_, and _j_th hole — at coordinate _p__j_. _j_th hole has enough room for _c__j_ mice, so not more than _c__j_ mice can enter this hole.
What is the minimum sum of distances that mice have to go through so that they all can hide in the holes? If _i_th mouse goes to the hole _j_, then its distance is |_x__i_ - _p__j_|.
Print the minimum sum of distances.
## Input
The first line contains two integer numbers _n_, _m_ (1 ≤ _n_, _m_ ≤ 5000) — the number of mice and the number of holes, respectively.
The second line contains _n_ integers _x_1, _x_2, ..., _x__n_ ( - 109 ≤ _x__i_ ≤ 109), where _x__i_ is the coordinate of _i_th mouse.
Next _m_ lines contain pairs of integer numbers _p__j_, _c__j_ ( - 109 ≤ _p__j_ ≤ 109, 1 ≤ _c__j_ ≤ 5000), where _p__j_ is the coordinate of _j_th hole, and _c__j_ is the maximum number of mice that can hide in the hole _j_.
## Output
Print one integer number — the minimum sum of distances. If there is no solution, print _\-1_ instead.
[samples]
一天，Masha 回家后发现走廊里有 #cf_span[n] 只老鼠。当然，她大声喊叫，吓得老鼠们开始向走廊中的洞穴跑去。
走廊可以表示为一条数轴，上面有 #cf_span[n] 只老鼠和 #cf_span[m] 个洞穴。第 #cf_span[i] 只老鼠位于坐标 #cf_span[xi]，第 #cf_span[j] 个洞穴位于坐标 #cf_span[pj]。第 #cf_span[j] 个洞穴最多能容纳 #cf_span[cj] 只老鼠，因此最多有 #cf_span[cj] 只老鼠可以进入该洞穴。
求老鼠们躲进洞穴所需的最小总距离。如果第 #cf_span[i] 只老鼠进入第 #cf_span[j] 个洞穴，则其距离为 #cf_span[|xi - pj|]。
请输出最小总距离。
第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n, m ≤ 5000]) —— 分别表示老鼠和洞穴的数量。
第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn] (#cf_span[ - 109 ≤ xi ≤ 109])，其中 #cf_span[xi] 表示第 #cf_span[i] 只老鼠的坐标。
接下来 #cf_span[m] 行，每行包含一对整数 #cf_span[pj, cj] (#cf_span[ - 109 ≤ pj ≤ 109, 1 ≤ cj ≤ 5000])，其中 #cf_span[pj] 是第 #cf_span[j] 个洞穴的坐标，#cf_span[cj] 是该洞穴最多可容纳的老鼠数量。
输出一个整数 —— 最小总距离。如果无解，请输出 _-1_。
## Input
第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n, m ≤ 5000]) —— 分别表示老鼠和洞穴的数量。第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn] (#cf_span[ - 109 ≤ xi ≤ 109])，其中 #cf_span[xi] 表示第 #cf_span[i] 只老鼠的坐标。接下来 #cf_span[m] 行，每行包含一对整数 #cf_span[pj, cj] (#cf_span[ - 109 ≤ pj ≤ 109, 1 ≤ cj ≤ 5000])，其中 #cf_span[pj] 是第 #cf_span[j] 个洞穴的坐标，#cf_span[cj] 是该洞穴最多可容纳的老鼠数量。
## Output
输出一个整数 —— 最小总距离。如果无解，请输出 _-1_。
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ be the number of mice and holes, respectively.
Let $ X = (x_1, x_2, \dots, x_n) \in \mathbb{R}^n $ be the coordinates of the mice.
Let $ H = \{(p_1, c_1), (p_2, c_2), \dots, (p_m, c_m)\} $ be the set of holes, where $ p_j \in \mathbb{R} $ is the coordinate of hole $ j $ and $ c_j \in \mathbb{Z}^+ $ is its capacity.
**Constraints**
1. $ 1 \le n, m \le 5000 $
2. $ -10^9 \le x_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $
3. $ -10^9 \le p_j \le 10^9 $ and $ 1 \le c_j \le 5000 $ for all $ j \in \{1, \dots, m\} $
4. Total capacity: $ \sum_{j=1}^m c_j \ge n $ (otherwise, no solution exists)
**Objective**
Minimize the total distance:
$$
\min \sum_{i=1}^n |x_i - p_{j(i)}|
$$
subject to:
- Each mouse $ i $ is assigned to exactly one hole $ j(i) \in \{1, \dots, m\} $,
- Each hole $ j $ is assigned at most $ c_j $ mice, i.e., $ |\{i \mid j(i) = j\}| \le c_j $.
If $ \sum_{j=1}^m c_j < n $, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "F. Mice and Holes",
"description": {
"content": "One day Masha came home and noticed _n_ mice in the corridor of her flat. Of course, she shouted loudly, so scared mice started to run to the holes in the corridor. The corridor can be represeted as ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF797F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "One day Masha came home and noticed _n_ mice in the corridor of her flat. Of course, she shouted loudly, so scared mice started to run to the holes in the corridor.\n\nThe corridor can be represeted as ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "一天，Masha 回家后发现走廊里有 #cf_span[n] 只老鼠。当然，她大声喊叫，吓得老鼠们开始向走廊中的洞穴跑去。\n\n走廊可以表示为一条数轴，上面有 #cf_span[n] 只老鼠和 #cf_span[m] 个洞穴。第 #cf_span[i] 只老鼠位于坐标 #cf_span[xi]，第 #cf_span[j] 个洞穴位于坐标 #cf_span[pj]。第 #cf_span[j] 个洞穴最...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ be the number of mice and holes, respectively. \nLet $ X = (x_1, x_2, \\dots, x_n) \\in \\mathbb{R}^n $ be the coordinates of the mice. \nLet $ H = \\{(p_1,...",
"is_translate": false,
"language": "Formal"
}
]
}