You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

T4:不死

限制

• 1000 ms
• 131072 KB

文件

survive

子曰：不睡觉就会死。

深信此话的 LYM 决定在本学期接下来的 $n$ 节课上考虑一下睡觉的问题。LYM 认为如果在一堂课上睡觉，身体的疲劳值就会下降，反之如果在一堂课上不睡觉，身体的疲劳值就会上升。而身体对疲劳的忍耐是有限度的，一旦疲劳值超过限度，LYM 就会死，于是他不得不在一些课上睡觉。注意，LYM 的疲劳值只会在一节课上完后发生改变，如果上完最后一节课后，疲劳值超出了限度，LYM 仍然会死。

不过，在不同的课上，疲劳值的变化量并不总是一样，就如在班主任的课上睡觉，疲劳值并不会下降太多，因为那样会睡得很不安心。

LYM 是一个死要面子的人，他宁可冒着生命危险，也要挽回自己在老师心中的形象，因此他不能总是在人家的课上睡觉。他给自己定下了一个规矩：决不连续地在同一主科的课上睡觉，即如果 LYM 在主科 X 的某堂课上睡了觉，那么在下一堂（不一定是相邻的）主科 X 的课上，LYM 就绝不会睡觉。

经过了这 $n$ 节课后，LYM 竟然没有死，LYM 想知道自己对疲劳值的忍耐极限至少是多少？

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个正整数，表示这 $n$ 节课的课程安排。每个整数代表一门课程，科目代号对应关系参见下文的表格。（$1\sim6$ 号学科均为主科，$7$ 号学科不算作主科）。

第三行，$n$ 个正整数，其中第 $i$ 个数表示在第 $i$ 节课上睡觉，疲劳值的减少量。

第四行，$n$ 个正整数，其中第 $i$ 个数表示在第 $i$ 节课上不睡觉，疲劳值的增加量。

第五行，一个整数，表示 LYM 的初始疲劳值。如果初始疲劳值大于了忍耐限度，LYM 会在第一节课前就暴亡。

输出格式

一个整数，表示 LYM 的忍耐限度的最小可能值。

样例输入 1

5
7 4 4 5 4
1 6 6 4 4
6 3 8 7 7
8

样例输出 1

9

样例输入 2

3
6 6 7
3 4 5
5 4 3
-1

样例输出 2

0

数据范围

对于 $20\%$ 的数据，有且仅有一门主科。

对于 $100\%$ 的数据，$1\leq n\leq 5000$，第三、四行的数据保证大于等于 $0$。

保证所有输入和输出都在 $[-2000000000,2000000000]$ 范围内。

没有说明是正整数的数据不保证为正。