← 返回题目列表

Codeforces · 988/F

F. 雨和雨伞

中文机器翻译题面 查看原题

Polycarp 生活在 $$$x = 0$$$ 点的坐标线上。他去找他住在 $$$x = a$$$ 的朋友。波利卡普只能从左向右移动,他每秒可以通过一个长度单位。

现在正在下雨,所以他的一些路段都在雨中。形式上,$$$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$$$。当波利卡普开始他的旅程时,他没有雨伞。

在从 $$$x = 0$$$ 到 $$$x = a$$$ 的旅程中,Polycarp 可以捡起和扔掉雨伞。波利卡普立即捡起并扔掉任何一把雨伞。他可以随时携带任意数量的雨伞。因为波利卡普不想被淋湿,所以如果 $$$[x, x + 1]$$$ 段在雨中(即,如果存在一些 $$$i$$$ 使得 $$$l_i \le x$$$ 和 $$$x + 1 \le r_i$$$),他在从 $$$x$$$ 移动到 $$$x + 1$$$ 时必须携带至少一把雨伞。

上述条件是唯一的要求。例如,可以在没有任何雨伞的情况下到达某个雨段开始的点,在该点拿起雨伞并沿着雨伞移动。波利卡普在雨中时可以交换雨伞。

每经过一个长度单位,坡旅甲普的疲劳度就会增加,其疲劳程度相当于他移动时携带的雨伞重量的总和。

坡旅甲能从 $$$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$$$ 后的最小总疲劳度。

示例

输入 #1

10 2 4
3 7
8 10
0 10
3 4
8 1
1 2

输出 #1

14

输入 #2

10 1 1
0 9
0 5

输出 #2

45

输入 #3

10 1 1
0 9
1 5

输出 #3

-1

注意

在第一个例子中,唯一可能的策略是在$$$x = 1$$$处拿第四把伞,一直保持到$$$x = 7$$$($$$x = 7$$$处的总疲劳将等于$$$12$$$),扔掉它,从$$$x = 7$$$继续到$$$x = 8$$$,不带伞,拿在 $$$x = 8$$$ 处打开第三把雨伞并保留到最后($$$x = 10$$$ 处的总疲劳将等于 $$$14$$$)。

在第二个例子中,唯一可能的策略是拿第一把伞,带着它移动直到$$$x = 9$$$,扔掉它并继续不带伞直到最后。