时间限制： 4.0 秒

空间限制： 512 MB

题目描述

David 是某大型科技公司的系统架构师，公司内部有一个复杂的任务调度系统，David 每次想要执行一个任务的时候，都需要同时执行一系列符合特定规则的任务集合。David 需要在满足要求的同时最大化执行任务造成的收益。这些任务的关系可以描述为一张有 $n$ 个节点，$m$ 条边的有向图 $G$，其中每个节点代表一个任务，每条边代表一定的依赖关系。我们的要求是，每个任务都有一个级别编号 $1\le d_i\le 10$，如果你要做这个任务，那么你必须要把所有的该任务在图上可达且级别编号小于等于改点的所有任务都做完；换言之，我们称一个任务集合 $S\subseteq \{1,2,\cdots,n\}$ 称为合法集合，如果 $S$ 满足 $\forall ~i\in S,j\in\{1,2,\cdots,n\}$，若 $d_i\ge d_j$ 且在图上存在一条从 $i$ 到 $j$ 的有向路径，那么一定有 $j\in S$。另外，每个任务有一个权重 $w_i$，代表执行该任务所能获得的收益，这个收益有可能是负的。David 的目标是找到权重和最大的合法集合的权重和。

例如，如下的有向图中，我们级节点为 $\{1,2,3,4,5,6\}$，对应每个点的级别编号也是 $\{1,2,3,4,5,6\}$。对如下有向图，方框内的标识为权值，圆圈内的标识为级别编号，$\{1,2,3,5\}$ 权值为 $1$，是一个合法的集合；$\{2,6\}$ 权值为 $5$，但不是一个合法的集合，因为 $6$ 号节点可达编号比它更小的 $5$ 号节点，但 $5$ 不属于这个集合。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n,m$，分别表示有向图 的点数和边数。

第二行包含 $n$ 个整数 $d_1,d_2,\cdots, d_n$ 表示 $n$ 个点的级别编号。

第三行包含 $n$ 个整数 $w_1,w_2,\cdots,w_n$ 表示 $n$ 个点的权重。

接下来 $m$ 行，每行包含两个整数 $u,v$ 满足 $1\le u,v\le n$ 且 $u\ne v$，代表点 $u$ 到点 $v$ 有一条有向边。

输出格式

输出到标准输出。

输出一个整数，代表权重和最大的合法集合的权重和。

6 8
1 2 3 4 5 6
1 2 3 -1 -5 3
1 2
2 1
6 2
6 3
5 3
4 2
6 5
4 5

6

样例 1 解释

对应的图 $G$ 如图所示，最大权集合为 $\{1,2,3\}$。

子任务

对于所有的数据，满足 $1\le m\le \min(n\cdot (n-1),10^5),~-10^5\le w_i\le 10^5,~1\le d_i\le 10$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。