题目描述

系统由$n$个任务组成，任务运行有依赖关系，前序任务执行完毕才可以启动后续任务。任务在启动前申请内存，执行完毕后释放，内存释放后可用于其他任务使用。解除依赖后的任务会直接由操作系统调度，分配内存，进入运行状态。每个任务的运行时间相等。请计算系统所有任务执行所需要的最小内存。

输入

第$1$行为$1$个正整数$n$，表示任务个数，$n<20$

第$2$行为$n$个正整数，表示每个任务所需要的内存大小，$0<内存<1000$

第$3$行为$n$个取值为$0$或$1$的数，表示任务$0$对其他任务的依赖关系，$0$表示不依赖，$1$表示依赖

....

第$3+n$行为$n$个取值为$0$或$1$的数，表示任务$n-1$对其他任务的依赖关系，$0$表示不依赖，$1$表示依赖

输出

输出系统任务执行所需要的最小内存

样例

输入

9
50 50 80 40 40 40 60 60 60
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 1 0

输出

120

解释

第一行:$9$，表示有$9$个任务 第二行: $50$ $50$ $80$ $40$ $40$ $40$ $60$ $60$ $60$，表示任务$t0~08$需要的内存大小

第三行:$0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$，表示$t$不依赖任务其他任务 第四行:$10$ $0$ $0$ $0$ $0$ $0$ $0$ $0$，表示$t1$依赖$t0$

第五行:$01$ $0$ $0$ $0$ $0$ $0$ $0$ $0$，表示$t2$依赖$t1$

~

任务的关系用图表示

1. 执行$t0$，分配$m0=50$，占用空间$[0,50)$，最大访问地址为$50$
2. 执行$t1$，分配$m1=50$，占用空间$[0,50)$，最大访问地址为$50$
3. 并发执行$t2$和$t5$，分配$m2=80$，$m5=40$，占用空间$[0,120)$，最大访问地址为120
4. 执行$t3$，分配$m3=40$，占用空间$[0,40)$，最大访问地址$40$
5. 并发执行$t4$和$t7$，分配$m4=40$，$m7=60$，占用空间$[0,100)$
6. 执行$t6$，分配$m6=60$，占用空间$[0,60)$，最大访问地址$60$
7. 执行$t8$，分配$m8=60$，占用空间$[0,60)$，最大访问地址$60$

输出系统的需要的最小内存为$120$

样例2

输入

10
40 50 80 10 30 80 90 30 70 150
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0

输入

190