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]$ 范围内。

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

样例 1 解释
问题背景
LYM 需要在 5 节课中选择睡觉或不睡觉，需满足主科（1-6）不能连续睡觉的规则，同时确保全程疲劳值不超过某个限度，目标是找到这个最小限度。
样例 1 输入解析
课程安排：[7,4,4,5,4]（7 是非主科，4、5 是主科）
睡觉减少量：[1,6,6,4,4]（每节课睡觉后疲劳值减少的数值）
不睡觉增加量：[6,3,8,7,7]（每节课不睡觉后疲劳值增加的数值）
初始疲劳值：8
关键过程分析
需要跟踪每节课后的状态（主科上一次是否睡觉）、当前疲劳值及过程中最大疲劳值，核心是通过动态规划保留最优解。

初始状态：
无课程处理时，状态为 0（所有主科均未睡觉），初始疲劳值 8，最大疲劳值 8（初始值必须≤限度）。
第 1 节课（科目 7，非主科）：
可自由选择睡觉或不睡觉：
睡觉：疲劳值 = 8-1=7，最大疲劳值 = 8（状态不变）。
不睡觉：疲劳值 = 8+6=14，最大疲劳值 = 14（状态不变）。
保留更优的（7,8）（因 8＜14）。
第 2 节课（科目 4，主科）：
主科 4 的上一次状态为 0（未睡觉），可选择睡或不睡：
睡觉：疲劳值 = 7-6=1，最大疲劳值 = 8，状态更新为 8（主科 4 标记为 “睡过”）。
不睡觉：疲劳值 = 7+3=10，最大疲劳值 = 10，状态保持 0。
保留（1,8）和（10,10）。
第 3 节课（科目 4，主科）：
若前状态为 8（主科 4 睡过）：必须不睡觉，疲劳值 = 1+8=9，最大疲劳值 = 9，状态重置为 0。
若前状态为 0（主科 4 未睡）：可睡（疲劳值 = 10-6=4，最大 10，状态 8）或不睡（疲劳值 = 10+8=18，最大 18，状态 0）。
保留（9,9）和（4,10）（18 被 9 支配，舍弃）。
第 4 节课（科目 5，主科）：
主科 5 的上一次状态为 0（未睡），可自由选择：
基于状态 0（疲劳 9）：睡（疲劳 5，最大 9，状态 16）或不睡（疲劳 16，最大 16，状态 0）。
基于状态 8（疲劳 4）：睡（疲劳 0，最大 10，状态 24）或不睡（疲劳 11，最大 11，状态 8）。
保留（5,9）、（16,16）、（0,10）、（11,11）。
第 5 节课（科目 4，主科）：
综合前序状态，最终有效状态及最大疲劳值为：
状态 24：疲劳 1，最大 9；
状态 16：疲劳 7，最大 10；
状态 8：疲劳 12，最大 16；
状态 0：疲劳 18，最大 18。
结果
最小限度为所有可能最大疲劳值中的最小值，即9。