【题目描述】

物流网络中有一个编号为 $0$ 的物流中心和 $n$ 个服务站，服务站编号为 $1,2,\ldots,n$．从物流中心前往服务站 $i$，或从服务站 $i$ 返回物流中心，都需要恰好 $t_i$ 单位时间．

调度员在时刻 $0$ 位于物流中心．系统给出两类委托：

• 一份出发委托 $(a,x)$ 只能在时刻 $x$ 接受，并要求调度员此时位于物流中心．接受后，调度员立即出发，并在时刻 $x+t_a$ 到达服务站 $a$；
• 一份返回委托 $(b,y)$ 只能在时刻 $y$ 接受，并要求调度员此时位于服务站 $b$．接受后，调度员立即出发，并在时刻 $y+t_b$ 返回物流中心．

调度员只能通过接受委托在物流中心和服务站之间移动，也可以在当前位置等待任意长的时间．如果调度员恰好在时刻 $z$ 到达某处，那么他可以立即接受一份开始时刻同为 $z$、且出发地点为该处的委托．

每份委托至多接受一次，同一时刻至多接受一份委托．如果调度员没有在委托规定的时刻位于其出发地点，就不能接受这份委托．

请计算调度员最多能够接受多少份委托．最后接受的委托可以是出发委托，调度员不必在行动结束时返回物流中心．

---

【输入描述】

第一行输入三个整数 $n,m,l$，分别表示服务站数量、出发委托数量和返回委托数量．

第二行输入 $n$ 个整数 $t_1,t_2,\ldots,t_n$，其中 $t_i$ 表示物流中心与服务站 $i$ 之间的单程时间．

接下来的 $m$ 行中，第 $i$ 行输入两个整数 $a_i,x_i$，表示一份在时刻 $x_i$ 从物流中心前往服务站 $a_i$ 的出发委托．

接下来的 $l$ 行中，第 $i$ 行输入两个整数 $b_i,y_i$，表示一份在时刻 $y_i$ 从服务站 $b_i$ 返回物流中心的返回委托．

保证同一类委托中不存在两份服务站编号和开始时刻均相同的委托．出发委托与返回委托之间允许具有相同的服务站编号和开始时刻．

---

【输出描述】

输出一个整数，表示最多能够接受的委托数量．

---

【样例 1】

【样例 1 输入】

3 4 4
2 3 1
1 1
2 2
3 7
1 6
1 4
2 6
3 8
1 9

【样例 1 输出】

4

【样例 1 解释】

可以依次接受以下四份委托：

1. 时刻 $1$ 从物流中心前往服务站 $1$，时刻 $3$ 到达；
2. 等待至时刻 $4$，从服务站 $1$ 返回，时刻 $6$ 到达物流中心；
3. 在到达物流中心的同一时刻，从物流中心再次前往服务站 $1$，时刻 $8$ 到达；
4. 等待至时刻 $9$，从服务站 $1$ 返回物流中心．

不存在能够接受五份委托的方案．

---

【样例 2】

【样例 2 输入】

2 3 2
5 1
2 0
1 2
2 3
2 1
2 4

【样例 2 输出】

4

【样例 2 解释】

调度员可以在时刻 $0$ 前往服务站 $2$，在时刻 $1$ 返回物流中心，再在物流中心等到时刻 $3$ 前往服务站 $2$，最后在时刻 $4$ 从服务站 $2$ 回到物流中心．

最后一份出发委托之后不必返回物流中心．

---

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans．

该样例满足子任务 $1$ 的范围，其中 $m+l=16$．

---

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans．

该样例满足子任务 $2$ 的范围，其中 $m=l=15$，且不满足子任务 $1$ 的范围．

---

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans．

该样例满足子任务 $3$ 的特殊性质，即 $n=1$．

---

【样例 6】

见选手目录下的 Data/sample6.in 和 Data/sample6.ans．

该样例满足子任务 $4$ 的特殊性质：每个服务站至多有一份返回委托．

---

【样例 7】

见选手目录下的 Data/sample7.in 和 Data/sample7.ans．

该样例对应子任务 $5$，无特殊性质；其中 $n=80$，$m=l=3001$，并且存在服务站拥有多份返回委托．

---

【数据规模与约定】

对于所有测试数据，保证：

• $1\le n,m,l\le 2\times 10^5$；
• $1\le t_i\le 10^9$；
• $1\le a_i,b_i\le n$；
• $0\le x_i,y_i\le 10^{18}$．

子任务编号	分数	特殊性质
$1$	$10$	$m+l\le 18$
$2$	$25$	$m,l\le 3000$
$3$	$15$	$n=1$
$4$	$20$	每个服务站至多有一份返回委托
$5$	$30$	无特殊性质

每个测试点仅属于表中对应的一组；同一组内的所有测试点全部通过，才能获得该组分数．

时间限制：$3$ 秒．

内存限制：$512$ MiB．

---

【大样例下载链接】

点击下载本题选手目录