CF988F.Rain and Umbrellas

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.

Now 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$).

There 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.

During 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$).

The 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.

Each unit of length passed increases Polycarp's fatigue by the sum of the weights of umbrellas he carries while moving.

Can 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.

Polycarp 生活在坐标轴上的点 $x = 0$ 处。他要前往住在点 $x = a$ 的朋友家。Polycarp 只能从左向右移动，每秒恰好移动一个单位长度。

此时正在下雨，因此他路径上的一些区间处于雨中。形式化地说，共有 $n$ 个互不相交的雨中区间，其中第 $i$ 个雨中区间表示为 $[l_i, r_i]$（满足 $0 \le l_i \lt r_i \le a$）。

直线上还散落着 $m$ 把雨伞，第 $i$ 把雨伞位于点 $x_i$（满足 $0 \le x_i \le a$），重量为 $p_i$。Polycarp 出发时手中没有任何雨伞。

在从 $x = 0$ 到 $x = a$ 的旅途中，Polycarp 可以拾取和丢弃雨伞。他拾取或丢弃任意一把雨伞均瞬时完成。在任意时刻，他可携带任意数量的雨伞。由于 Polycarp 不想被淋湿，因此当他从 $x$ 移动到 $x + 1$ 时，若单位区间 $[x, x + 1]$ 完全处于雨中（即存在某个 $i$ 满足 $l_i \le x$ 且 $x + 1 \le r_i$），则他必须至少携带一把雨伞。

上述条件是唯一约束。例如，他可以不带任何雨伞走到某段雨区的起点位置，在该点拾起一把雨伞，然后持伞继续前进；Polycarp 也可以在雨中更换所持的雨伞。

每移动一个单位长度，Polycarp 的疲劳值将增加他当前所持所有雨伞的重量之和。

Polycarp 能否从点 $x = 0$ 成功到达点 $x = a$？如果可以，请找出他在最优地拾取与丢弃雨伞的前提下，抵达 $x = a$ 时的最小总疲劳值。

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.

Each 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$.

Each 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.

第一行包含三个整数 $a$、$n$ 和 $m$（$1 \le a, m \le 2000$，$1 \le n \le \lceil\frac{a}{2}\rceil$）——分别表示 Polycarp 的朋友所居住的位置、雨区线段的数量以及雨伞的数量。

接下来的 $n$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$0 \le l_i \lt r_i \le a$）——表示第 $i$ 个雨区线段的左右端点。保证任意两个雨区线段互不相交。换言之，对任意两个线段 $i$ 和 $j$，均有 $r_i \lt l_j$ 或 $r_j \lt l_i$。

再接下来的 $m$ 行中，每行包含两个整数 $x_i$ 和 $p_i$（$0 \le x_i \le a$，$1 \le p_i \le 10^5$）——分别表示第 $i$ 把雨伞的位置及其重量。

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.

如果 Polycarp 无法从点 $x = 0$ 到达点 $x = a$，则输出 \-1（不带引号）。否则，输出一个整数——即 Polycarp 在最优地拾取和丢弃雨伞的前提下，到达 $x = a$ 时的最小总疲劳值。

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$).

In 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.

在第一个例子中，唯一可行的策略是：在位置 $x = 1$ 处取第四把伞，一直携带至位置 $x = 7$（此时在 $x = 7$ 处的总疲劳值为 $12$），然后丢弃该伞；接着从 $x = 7$ 移动到 $x = 8$ 且不携带伞；在 $x = 8$ 处取第三把伞，并一直携带至终点（此时在 $x = 10$ 处的总疲劳值为 $14$）。

在第二个例子中，唯一可行的策略是：取第一把伞，携带它移动至位置 $x = 9$，然后丢弃该伞，并在剩余路程中不携带伞直至终点。