{"raw_statement":[{"iden":"statement","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 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.\n\nWhat 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_|.\n\nPrint the minimum sum of distances."},{"iden":"input","content":"The first line contains two integer numbers _n_, _m_ (1 ≤ _n_, _m_ ≤ 5000) — the number of mice and the number of holes, respectively.\n\nThe 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.\n\nNext _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_."},{"iden":"output","content":"Print one integer number — the minimum sum of distances. If there is no solution, print _\\-1_ instead."},{"iden":"examples","content":"Input\n\n4 5\n6 2 8 9\n3 6\n2 1\n3 6\n4 7\n4 7\n\nOutput\n\n11\n\nInput\n\n7 2\n10 20 30 40 50 45 35\n-1000000000 10\n1000000000 1\n\nOutput\n\n7000000130"}],"translated_statement":[{"iden":"statement","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] 个洞穴最多能容纳 #cf_span[cj] 只老鼠，因此最多有 #cf_span[cj] 只老鼠可以进入该洞穴。\n\n求老鼠们躲进洞穴所需的最小总距离。如果第 #cf_span[i] 只老鼠进入第 #cf_span[j] 个洞穴，则其距离为 #cf_span[|xi - pj|]。\n\n请输出最小总距离。\n\n第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n, m ≤ 5000]) —— 分别表示老鼠和洞穴的数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn] (#cf_span[ - 109 ≤ xi ≤ 109])，其中 #cf_span[xi] 表示第 #cf_span[i] 只老鼠的坐标。\n\n接下来 #cf_span[m] 行，每行包含一对整数 #cf_span[pj, cj] (#cf_span[ - 109 ≤ pj ≤ 109, 1 ≤ cj ≤ 5000])，其中 #cf_span[pj] 是第 #cf_span[j] 个洞穴的坐标，#cf_span[cj] 是该洞穴最多可容纳的老鼠数量。\n\n输出一个整数 —— 最小总距离。如果无解，请输出 _-1_。"},{"iden":"input","content":"第一行包含两个整数 #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] 是该洞穴最多可容纳的老鼠数量。"},{"iden":"output","content":"输出一个整数 —— 最小总距离。如果无解，请输出 _-1_。"},{"iden":"examples","content":"输入\n4 5\n6 2 8 9\n3 6\n2 1\n3 6\n4 7\n4 7\n输出\n11\n\n输入\n7 2\n10 20 30 40 50 45 35\n-1000000000 10\n1000000000 1\n输出\n7000000130"}],"sample_group":[],"show_order":[],"formal_statement":"**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, 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.\n\n**Constraints**  \n1. $ 1 \\le n, m \\le 5000 $  \n2. $ -10^9 \\le x_i \\le 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ -10^9 \\le p_j \\le 10^9 $ and $ 1 \\le c_j \\le 5000 $ for all $ j \\in \\{1, \\dots, m\\} $  \n4. Total capacity: $ \\sum_{j=1}^m c_j \\ge n $ (otherwise, no solution exists)\n\n**Objective**  \nMinimize the total distance:  \n$$\n\\min \\sum_{i=1}^n |x_i - p_{j(i)}|\n$$  \nsubject to:  \n- Each mouse $ i $ is assigned to exactly one hole $ j(i) \\in \\{1, \\dots, m\\} $,  \n- Each hole $ j $ is assigned at most $ c_j $ mice, i.e., $ |\\{i \\mid j(i) = j\\}| \\le c_j $.\n\nIf $ \\sum_{j=1}^m c_j < n $, output $ -1 $.","simple_statement":null,"has_page_source":false}