CF988F Rain and Umbrellas

Polycarp 住在坐标轴上的 $x = 0$ 点。他要去他朋友家，朋友住在 $x = a$ 点。Polycarp 只能从左向右移动，每秒可以前进 $1$ 个单位长度。 现在正在下雨，他的路上有一些区间正在下雨。具体来说，有 $n$ 个互不相交的下雨区间，第 $i$ 个下雨区间为 $[l_i, r_i]$（$0 \le l_i < r_i \le a$）。 路上有 $m$ 把伞，第 $i$ 把伞放在 $x_i$ 点（$0 \le x_i \le a$），重量为 $p_i$。Polycarp 出发时没有伞。 在从 $x = 0$ 走到 $x = a$ 的过程中，Polycarp 可以随时捡起或扔掉伞，捡起和扔掉伞都是瞬间完成的。他在任何时刻可以携带任意数量的伞。为了不被淋湿，如果他要经过 $[x, x+1]$ 这个区间，并且该区间在下雨（即存在某个 $i$ 使得 $l_i \le x$ 且 $x+1 \le r_i$），那么他必须至少携带一把伞。 上述是唯一的要求。例如，他可以不带伞走到某个下雨区间的起点，在那里捡起一把伞，然后带着伞继续前进。在下雨区间内他也可以换伞。 每经过 $1$ 个单位长度，他的疲劳值会增加他携带的所有伞的重量之和。 Polycarp 能否从 $x = 0$ 走到 $x = a$？如果可以，求他在最优策略下到达 $x = a$ 时的最小总疲劳值。

第一行包含三个整数 $a$、$n$ 和 $m$（$1 \le a, m \le 2000, 1 \le n \le \lceil\frac{a}{2}\rceil$），分别表示朋友的位置、下雨区间的数量和伞的数量。 接下来 $n$ 行，每行两个整数 $l_i$ 和 $r_i$（$0 \le l_i < r_i \le a$），表示第 $i$ 个下雨区间的左右端点。保证所有区间互不相交，即对于任意 $i, j$，要么 $r_i < l_j$，要么 $r_j < l_i$。 接下来 $m$ 行，每行两个整数 $x_i$ 和 $p_i$（$0 \le x_i \le a$，$1 \le p_i \le 10^5$），表示第 $i$ 把伞的位置和重量。

如果 Polycarp 无法从 $x = 0$ 走到 $x = a$，输出 $-1$。否则，输出一个整数，表示他到达 $x = a$ 时的最小总疲劳值。

在第一个样例中，唯一可行的策略是在 $x = 1$ 处拿起第 4 把伞，一直带到 $x = 7$（此时疲劳值为 $12$），然后扔掉伞，从 $x = 7$ 走到 $x = 8$ 不带伞，在 $x = 8$ 处拿起第 3 把伞并带到终点（此时疲劳值为 $14$）。 在第二个样例中，唯一可行的策略是拿起第 1 把伞，一直带到 $x = 9$，然后扔掉伞，剩下的路不带伞走到终点。 由 ChatGPT 4.1 翻译