题目描述

徐老师最近回归了一个著名老牌游戏——《魔兽世界》

在新版本中有一个单人副本模式《地下堡》，这可真是太利好徐老师这样的单人玩家了

于是徐老师在家里从早刷到晚，刷的昏天暗地，天旋地转

在梦里，徐老师依旧在刷地下堡，但是他梦到了一个神奇的地下堡副本，这个副本是一条直线，一共有 $n + 1$ 个房间排成一排编号分别为 $0 \sim n$，徐老师必须从 $0$ 号房间进入，从 $n$ 号房间结束副本

有些房间内存在 火焰喷射器，这个火焰喷射器会使得连续一段房间以及房间之间的走廊中都覆盖着火焰，徐老师一旦碰到火焰就会受到致命伤害导致游戏失败

有些房间内存在 护盾发生器，当拥有一个护盾发生器时，徐老师可以进入到有火焰的地方而不受伤害

当然，一个房间可能既被火焰覆盖，又有护盾发生器，甚至有好几个护盾发生器

也就是说，每次进入一个房间时，徐老师会 依次 进行以下行动或判定

1. 如果房间内有护盾发生器，徐老师可以选择拿起其中的某个护盾发生器
2. 如果该房间被火焰覆盖，则系统会判定徐老师身上是否有护盾发生器，若没有则游戏失败
3. 如果徐老师身上已经带有护盾发生器，徐老师可以选择放下身上的护盾发生器

而护盾发生器的重量可能不同，徐老师如果拿着一个重量为 $p$ 的护盾发生器从当前房间 移动到下一个房间，需要花费 $p$ 点体力

当然，徐老师身上可以同时携带多个护盾发生器，也可以在某个房间内放下多个护盾发生器

现在徐老师想知道，自己最少花费多少体力可以通关这个梦中副本？

P.S. 如果只是拿起放下护盾发生器，不会消耗体力

输入格式

输入第一行包含三个整数，$n, m, k$，分别表示有 $n + 1$ 个房间，$m$ 个火焰喷射器和 $k$ 个护盾发生器

接下来 $m$ 行每行包含两个整数 $l,r$ 表示第 $i$ 个火焰喷射器覆盖编号为 $l \sim r$ 的房间以及房间之间的走廊（包含编号为 $l$ 和 $r$ 的房间内）

接下来 $k$ 行每行包含两个整数 $x,p$ 表示第 $i$ 个护盾发生器在编号为 $x$ 的房间内，重量为 $p$

输出格式

输出一行包含一个整数，表示徐老师最小花费的体力

数据范围

对于 $30\%$ 的数据满足：$1 \leq n,m,k \leq 10$

对于 $100\%$ 的数据满足：$1 \leq n,m,k,p \leq 2000$

对于所有数据保证：

1. $m \leq n / 2, 1 \leq l < r \leq n, 0 \leq x \leq n$
2. 保证火焰喷射器的覆盖范围不会出现交叉，仅有可能在端点出重叠，且给定的 $l,r$ 不会重复
3. 火焰喷射器和护盾发生器的分布保证徐老师存在至少一种方案能够通关副本

样例输入1

3 2 3
1 2
2 3
0 3
1 2
3 1

样例输出1

4

样例解释1

不拿 $0$ 号房间的护盾发生器，到 $1$ 号房间拿起重量为 $2$ 的护盾发生器，一直走到 $3$ 号房间通关游戏，共计花费体力 $2 * 2=4$

样例输入2

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

样例输出2

14

样例解释2

在 $1$ 号房间拿起重量为 $2$ 的护盾发生器，到 $7$ 号房间经过火焰判定后丢下身上的护盾发生器，此时花费体力 $6 * 2 = 12$

然后移动到 $8$ 号房间，由于身上没有护盾发生器不花费体力

进入 $8$ 号房间时拿起 $8$ 号房间内重量为 $1$ 的护盾发生器，此时能够通过火焰判定，游戏不会失败

移动到 $10$ 号房间通关副本，此时花费体力 $2 * 1 = 2$

共计花费体力 $12+2=14$