人生大概就是这样。在这物欲横流的红尘紫陌中，芸芸众生为了生计四处奔走，交谈越来越少，感情越来越淡。但是，著名科学家 Access Globe 的最新研究成果可以解决这样的问题：通过增加同时做的事情来增加共同语言。
A 和 B 都得到了一些任务，设他们要执行的任务集合分别为 V_A 和 V_B。对每个人来说，任务 1 是必须一开始做的，而其他的每个任务 e 都存在一个前置任务 p_e，表示任务 e 必须在任务 p_e 完成后才能执行。也就是说，每个人的任务的依赖关系构成了一棵有根外向树，一个任务 e 能被执行当且仅当 p_e,p_pe,...,1 这些任务全部都被执行，称 p 依赖任务 p_e,p_pe,...,1 。
现在，A 和 B 希望他们能有一些任务是共同完成的，因此他们决定这样选出一些任务：A 选出 m 个任务 a₁,...,a_m，要求 a₁=1，并且对于任意的 1≤ i<m，都要求 a_i+1依赖任务 a_i；同时 B 也选出 m 个满足同样要求的任务 b₁,...,b_m，这样，A 就可以沿着从 1 到 A_m 的路径依次执行这些任务，同时 B 也可以沿着 1 到 B_m 的路径依次执行这些任务；并且经过安排，当 A 在执行任务 a_i 的时候，B 恰好在执行任务 b_i，在这时 A 和 B 就能取得联系，增进感情。

模型的目标为最大化亲密度。对于一组同时执行任务的关系 a_i 和 b_i，可以获得 C_ai,bi的得分；同时，A 和 B 一旦失去联系，就会使得亲密度降低，在每一分钟，如果一方距离上次和对方联系后已经执行任务 i 分钟，就会使得亲密度降低 2i-1。

例如，两个人要做的任务所花费的时间分别为 2,1,4,7 和 4,8,3,6,4，并且共同完成了第一个任务和最后一个任务，那么 A 在执行中间两个任务的 1+4=5 分钟没有和 B 联系，使得亲密度降低 1+3+...+11=25；同时 B 在执行中间三个任务的 8+3+6=17 分钟没有和 A 联系，使得亲密度降低 1+3+...+35=289。注意，亲密度的计算只和任务执行的时间有关；并且任意两个任务都可以作为 a_i 和 b_i 同时执行，不需要保证它们花费的时间相同。

现在，给出 A 和 B 的任务、依赖关系和每个任务的执行时间，请你帮我们求出能够获得的最大的亲密度。

第一行两个整数 |VA|,|VB|；
第二行|VA|-1 个整数 ，表示 A 的每个任务的时间长度；
第三行 |VA|-1 个整数，表示 B 的每个任务的时间长度；
第四行 |VA|-1 个整数，表示 A 的每个任务的前置任务，保证 ；
第五行 |VB|-1 个整数 ，表示 B 的每个任务的前置任务，保证 ；
接下来 |VA|-1 行，每行 |VB|-1 个整数，第 i-1 行第 j-1 列为 Ci,j，表示 A 和 B 同时分别执行对应的任务 i, j 能获得的亲密度，注意这些亲密度不一定是非负的；
注意以上输入均不包括第 1 个任务的信息，因为它和亲密度的计算没有关系。

输出能获得的最大的亲密度。

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

5

A 和 B 分别选出任务 1,3,4 和 1,2,3，同时执行的任务对 (1,1)、(3,2) 和 (4,3) 使得他们获得了 4+5=9 的亲密度；A 孤独地执行任务 2 的 2 分钟丢失了 1+3=4 的亲密度，因此最终的总亲密度为 9-4=5。这就是亲密度最大的方案。

对于所有数据，2≤ |VA|,|VB|≤ 2666，1≤ ≤ 1206，0≤ |Ci,j|≤ 2017011328。