{"raw_statement":[{"iden":"statement","content":"Polycarp lives on a coordinate line at the point $x = 0$. He goes to his friend that lives at the point $x = a$. Polycarp can move only from left to right, he can pass one unit of length each second.\n\nNow it's raining, so some segments of his way are in the rain. Formally, it's raining on $n$ non-intersecting segments, the $i$\\-th segment which is in the rain is represented as $[l_i, r_i]$ ($0 \\le l_i &lt; r_i \\le a$).\n\nThere are $m$ umbrellas lying on the line, the $i$\\-th umbrella is located at point $x_i$ ($0 \\le x_i \\le a$) and has weight $p_i$. When Polycarp begins his journey, he doesn't have any umbrellas.\n\nDuring his journey from $x = 0$ to $x = a$ Polycarp can pick up and throw away umbrellas. Polycarp picks up and throws down any umbrella instantly. He can carry any number of umbrellas at any moment of time. Because Polycarp doesn't want to get wet, he must carry at least one umbrella while he moves from $x$ to $x + 1$ if a segment $[x, x + 1]$ is in the rain (i.e. if there exists some $i$ such that $l_i \\le x$ and $x + 1 \\le r_i$).\n\nThe condition above is the only requirement. For example, it is possible to go without any umbrellas to a point where some rain segment starts, pick up an umbrella at this point and move along with an umbrella. Polycarp can swap umbrellas while he is in the rain.\n\nEach unit of length passed increases Polycarp's fatigue by the sum of the weights of umbrellas he carries while moving.\n\nCan Polycarp make his way from point $x = 0$ to point $x = a$? If yes, find the minimum total fatigue after reaching $x = a$, if Polycarp picks up and throws away umbrellas optimally."},{"iden":"input","content":"The first line contains three integers $a$, $n$ and $m$ ($1 \\le a, m \\le 2000, 1 \\le n \\le \\lceil\\frac{a}{2}\\rceil$) — the point at which Polycarp's friend lives, the number of the segments in the rain and the number of umbrellas.\n\nEach of the next $n$ lines contains two integers $l_i$ and $r_i$ ($0 \\le l_i &lt; r_i \\le a$) — the borders of the $i$\\-th segment under rain. **It is guaranteed that there is no pair of intersecting segments**. In other words, for each pair of segments $i$ and $j$ either $r_i &lt; l_j$ or $r_j &lt; l_i$.\n\nEach of the next $m$ lines contains two integers $x_i$ and $p_i$ ($0 \\le x_i \\le a$, $1 \\le p_i \\le 10^5$) — the location and the weight of the $i$\\-th umbrella."},{"iden":"output","content":"Print \"_\\-1_\" (without quotes) if Polycarp can't make his way from point $x = 0$ to point $x = a$. Otherwise print one integer — the minimum total fatigue after reaching $x = a$, if Polycarp picks up and throws away umbrellas optimally."},{"iden":"examples","content":"Input\n\n10 2 4\n3 7\n8 10\n0 10\n3 4\n8 1\n1 2\n\nOutput\n\n14\n\nInput\n\n10 1 1\n0 9\n0 5\n\nOutput\n\n45\n\nInput\n\n10 1 1\n0 9\n1 5\n\nOutput\n\n\\-1"},{"iden":"note","content":"In the first example the only possible strategy is to take the fourth umbrella at the point $x = 1$, keep it till the point $x = 7$ (the total fatigue at $x = 7$ will be equal to $12$), throw it away, move on from $x = 7$ to $x = 8$ without an umbrella, take the third umbrella at $x = 8$ and keep it till the end (the total fatigue at $x = 10$ will be equal to $14$).\n\nIn the second example the only possible strategy is to take the first umbrella, move with it till the point $x = 9$, throw it away and proceed without an umbrella till the end."}],"translated_statement":[{"iden":"statement","content":"Polycarp 位于坐标轴上的点 $x = 0$。他要去位于点 $x = a$ 的朋友家。Polycarp 只能从左向右移动，每秒移动一个单位长度。\n\n现在正在下雨，因此他路径上的某些段处于雨中。具体来说，有 $n$ 个互不相交的雨区段，第 $i$ 个雨区段表示为 $[ l_i, r_i ]$（$0 lt.eq l_i < r_i lt.eq a$）。\n\n有 $m$ 把伞分布在坐标轴上，第 $i$ 把伞位于点 $x_i$（$0 lt.eq x_i lt.eq a$），重量为 $p_i$。当 Polycarp 开始旅程时，他没有任何伞。\n\n在从 $x = 0$ 到 $x = a$ 的旅途中，Polycarp 可以随时捡起或丢弃伞。他捡起或放下任何伞都是瞬间完成的。在任意时刻，他可以携带任意数量的伞。为了不被淋湿，当他从 $x$ 移动到 $x + 1$ 时，如果线段 $[ x, x + 1 ]$ 处于雨中（即存在某个 $i$ 使得 $l_i lt.eq x$ 且 $x + 1 lt.eq r_i$），他必须携带至少一把伞。\n\n上述条件是唯一要求。例如，他可以在没有伞的情况下走到某个雨区段的起点，在该点捡起一把伞，然后继续携带伞前进。Polycarp 在雨中也可以更换伞。\n\n每移动一个单位长度，他的疲劳值会增加他当前携带的所有伞的重量之和。\n\nPolycarp 能否从点 $x = 0$ 到达点 $x = a$？如果可以，请找出在最优地捡起和丢弃伞的情况下，到达 $x = a$ 时的最小总疲劳值。\n\n第一行包含三个整数 $a$, $n$ 和 $m$（$1 lt.eq a, m lt.eq 2000$, $1 lt.eq n lt.eq lceil frac(a, 2) rceil$）——分别表示 Polycarp 朋友家的位置、雨区段的数量和伞的数量。\n\n接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$0 lt.eq l_i < r_i lt.eq a$）——表示第 $i$ 个雨区段的边界。*保证不存在相交的雨区段*，即对于任意两个雨区段 $i$ 和 $j$，要么 $r_i < l_j$，要么 $r_j < l_i$。\n\n接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $p_i$（$0 lt.eq x_i lt.eq a$, $1 lt.eq p_i lt.eq 10^5$）——表示第 $i$ 把伞的位置和重量。\n\n如果 Polycarp 无法从 $x = 0$ 到达 $x = a$，请输出 \"_-1_\"（不含引号）；否则输出一个整数——Polycarp 在最优地捡起和丢弃伞的情况下，到达 $x = a$ 时的最小总疲劳值。\n\n在第一个例子中，唯一可行的策略是：在 $x = 1$ 处捡起第四把伞，一直携带到 $x = 7$（此时总疲劳值为 $12$），然后丢弃它；从 $x = 7$ 移动到 $x = 8$ 时不携带伞；在 $x = 8$ 处捡起第三把伞，并一直携带到终点（到达 $x = 10$ 时总疲劳值为 $14$）。\n\n在第二个例子中，唯一可行的策略是：捡起第一把伞，携带它直到 $x = 9$，然后丢弃它，之后不携带伞走到终点。"},{"iden":"input","content":"第一行包含三个整数 $a$, $n$ 和 $m$（$1 lt.eq a, m lt.eq 2000$, $1 lt.eq n lt.eq lceil frac(a, 2) rceil$）——分别表示 Polycarp 朋友家的位置、雨区段的数量和伞的数量。接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$0 lt.eq l_i < r_i lt.eq a$）——表示第 $i$ 个雨区段的边界。*保证不存在相交的雨区段*，即对于任意两个雨区段 $i$ 和 $j$，要么 $r_i < l_j$，要么 $r_j < l_i$。接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $p_i$（$0 lt.eq x_i lt.eq a$, $1 lt.eq p_i lt.eq 10^5$）——表示第 $i$ 把伞的位置和重量。"},{"iden":"output","content":"如果 Polycarp 无法从 $x = 0$ 到达 $x = a$，请输出 \"_-1_\"（不含引号）；否则输出一个整数——Polycarp 在最优地捡起和丢弃伞的情况下，到达 $x = a$ 时的最小总疲劳值。"},{"iden":"examples","content":"输入1\n10 2 4\n3 7\n8 10\n0 10\n3 4\n8 1\n1 2\n输出1\n14\n\n输入2\n10 1 1\n0 9\n0 5\n输出2\n45\n\n输入3\n10 1 1\n0 9\n1 5\n输出3\n-1"},{"iden":"note","content":"在第一个例子中，唯一可行的策略是：在 $x = 1$ 处捡起第四把伞，一直携带到 $x = 7$（此时总疲劳值为 $12$），然后丢弃它；从 $x = 7$ 移动到 $x = 8$ 时不携带伞；在 $x = 8$ 处捡起第三把伞，并一直携带到终点（到达 $x = 10$ 时总疲劳值为 $14$）。在第二个例子中，唯一可行的策略是：捡起第一把伞，携带它直到 $x = 9$，然后丢弃它，之后不携带伞走到终点。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ a \\in \\mathbb{Z}^+ $ be the destination point.\n- Let $ \\mathcal{R} = \\{ [l_i, r_i) \\}_{i=1}^n $ be a set of $ n $ non-overlapping rain segments, where each segment $ [l_i, r_i) $ denotes that the interval from $ x = l_i $ to $ x = r_i - 1 $ is under rain (i.e., movement from $ x $ to $ x+1 $ is rainy for all $ x \\in [l_i, r_i - 1] $).\n- Let $ \\mathcal{U} = \\{ (x_j, p_j) \\}_{j=1}^m $ be a set of $ m $ umbrellas, where $ x_j \\in [0, a] $ is the position and $ p_j \\in \\mathbb{Z}^+ $ is the weight of umbrella $ j $.\n\n**Constraints:**\n\n- Polycarp starts at $ x = 0 $ with no umbrellas.\n- Polycarp moves only rightward, one unit per second, from $ x = 0 $ to $ x = a $.\n- For each integer position $ x \\in [0, a-1] $, if $ [x, x+1] \\subseteq [l_i, r_i) $ for some $ i $, then Polycarp **must** carry at least one umbrella during the move from $ x $ to $ x+1 $.\n- At any integer point $ x \\in [0, a] $, Polycarp may pick up or drop any subset of umbrellas located at $ x $ (instantly).\n- Polycarp may carry any number of umbrellas simultaneously.\n- The fatigue incurred during the move from $ x $ to $ x+1 $ is equal to the **sum of the weights of all umbrellas carried** during that move.\n\n**Objective:**\n\nFind the **minimum total fatigue** over the entire journey from $ x = 0 $ to $ x = a $, under the constraint that every rainy segment $ [x, x+1] $ is covered by at least one carried umbrella.\n\nIf no valid strategy exists, output $ -1 $.\n\n---\n\n**Formal Problem Statement:**\n\nLet $ S \\subseteq \\{0, 1, \\dots, a-1\\} $ be the set of integer positions where movement is in the rain:  \n$$\nS = \\bigcup_{i=1}^n \\{ l_i, l_i+1, \\dots, r_i - 1 \\}\n$$\n\nLet $ U(x) \\subseteq \\mathcal{U} $ be the set of umbrellas located at position $ x $, i.e.,  \n$$\nU(x) = \\{ (x_j, p_j) \\in \\mathcal{U} \\mid x_j = x \\}\n$$\n\nLet $ c(x) \\in \\mathbb{R}_{\\geq 0} $ be the total weight of umbrellas carried by Polycarp during the move from $ x $ to $ x+1 $, for $ x = 0, 1, \\dots, a-1 $.\n\n**Constraints on $ c(x) $:**\n- $ c(x) \\geq \\min\\left\\{ \\sum_{j \\in I} p_j \\mid I \\subseteq U(x) \\cup \\text{previously carried umbrellas}, \\text{and } c(x) > 0 \\right\\} $ if $ x \\in S $,\n- $ c(x) \\geq 0 $ for all $ x \\in [0, a-1] $,\n- $ c(x) = 0 $ if $ x \\notin S $,\n- $ c(x) $ is the sum of weights of umbrellas carried during step $ x \\to x+1 $, and may change only at integer positions (i.e., at $ x \\in \\{0, 1, \\dots, a\\} $).\n\nLet $ \\mathcal{C} $ be the set of all valid sequences $ (c(0), c(1), \\dots, c(a-1)) $ satisfying the above.\n\n**Objective:**\n$$\n\\min_{(c(0), \\dots, c(a-1)) \\in \\mathcal{C}} \\sum_{x=0}^{a-1} c(x)\n$$\n\n**Additional constraint:** At each position $ x \\in \\{0, 1, \\dots, a\\} $, the set of carried umbrellas must be a subset of $ \\bigcup_{y=0}^{x} U(y) $, and any umbrella dropped at $ x $ must have been carried since its pickup at some $ y \\leq x $.\n\n---\n\n**Note:** The problem reduces to a dynamic programming problem over positions $ x = 0 $ to $ a $, where the state is the set of umbrellas currently carried. However, since $ m \\leq 2000 $, a direct subset DP is infeasible. Instead, we exploit the fact that **only umbrella weights matter**, and **at any position, we only need to know the minimal total weight required to cover the current and future rain segments**.\n\nBut for **formal mathematical representation**, we define the problem as above.\n\n---\n\n**Final Formal Statement:**\n\nLet $ \\mathcal{R} $ be a set of non-overlapping rain intervals $ [l_i, r_i) \\subseteq [0, a) $, and $ \\mathcal{U} $ a multiset of umbrellas $ (x_j, p_j) $ with $ x_j \\in [0, a] $, $ p_j > 0 $.\n\nDefine the set of required covered steps:\n$$\nS = \\bigcup_{i=1}^n \\{ l_i, l_i+1, \\dots, r_i - 1 \\}\n$$\n\nLet $ \\mathbf{c} = (c_0, c_1, \\dots, c_{a-1}) \\in \\mathbb{R}_{\\geq 0}^a $ be a vector where $ c_x $ is the total weight of umbrellas carried during step $ x \\to x+1 $.\n\nDefine the set of feasible $ \\mathbf{c} $ as those satisfying:\n\n1. $ c_x \\geq \\min \\left\\{ \\sum_{j \\in I} p_j \\,\\middle|\\, I \\subseteq \\bigcup_{y=0}^{x} U(y), \\text{ and } \\text{umbrellas in } I \\text{ were picked up at } y \\leq x \\text{ and not dropped before } x \\right\\} $ for all $ x \\in S $,\n2. $ c_x = 0 $ for all $ x \\notin S $,\n3. For each umbrella $ (x_j, p_j) $, if picked up at $ x_j $, it may be dropped only at some $ x \\geq x_j $, and contributes to $ c_x $ for all $ x \\in [x_j, d_j) $ where $ d_j $ is the drop position.\n\nThen, the problem is:\n\n$$\n\\boxed{\n\\min_{\\mathbf{c} \\in \\mathcal{F}} \\sum_{x=0}^{a-1} c_x\n}\n$$\n\nwhere $ \\mathcal{F} $ is the set of all feasible $ \\mathbf{c} $ satisfying the above constraints.\n\nIf $ \\mathcal{F} = \\emptyset $, output $ -1 $.","simple_statement":null,"has_page_source":false}