#P10111. [GESP202312 七级] 纸牌游戏

[GESP202312 七级] 纸牌游戏

题目描述

你和小杨在玩一个纸牌游戏。

你和小杨各有 33 张牌,分别是 0120、1、2 。你们要进行 NN 轮游戏,每轮游戏双方都要出一张牌,并按 11 战胜 0022 战胜 1100 战胜 22 的规则决出胜负。第 ii 轮的胜者可以获得 2×ai2×a_i 分,败者不得分,如果双方出牌相同,则算平局,二人都可获得 aia_ii=1,2,,N(i=1,2,…,N)

玩了一会后,你们觉得这样太过于单调,于是双方给自己制定了不同的新规则。小杨会在整局游戏开始前确定自己全部 nn 轮的出牌,并将他的全部计划告诉你;而你从第 22 轮开始,要么继续出上一轮出的牌,要么记一次“换牌”。游戏结束时,你换了 tt 次牌,就要额外扣 b1++btb_1+…+b_t 分。

请计算出你最多能获得多少分。

输入格式

第一行一个整数 NN,表示游戏轮数。

第二行 N N 个用单个空格隔开的非负整数 a1,,aNa_1,…,a_N ,意义见题目描述。

第三行 N1N-1 个用单个空格隔开的非负整数 b1,,bN1b_1,\cdots,b_{N-1} ,表示换牌的罚分,具体含义见题目描述。由于游戏进行 N 轮,所以你至多可以换 N1N-1 次牌。

第四行 NN 个用单个空格隔开的整数 c1,,,cNc_1,,\cdots,c_N ,依次表示小杨从第 11 轮至第 NN 轮出的牌。保证 ci0,1,2c _i\in{0,1,2}

输出格式

一行一个整数,表示你最多获得的分数。

4
1 2 10 100
1 100 1
1 1 2 0
219
6
3 7 2 8 9 4
1 3 9 27 81
0 1 2 1 2 0
56

提示

样例解释 1

你可以第 11 轮出 00,并在第 2,32,3 轮保持不变,如此输掉第 1,21,2 轮,但在第 33 轮中取胜,获得 2×10=202×10=20 分;

随后,你可以在第 44 轮中以扣 11 分为代价改出 11 ,并在第 44 轮中取得胜利,获得 2×100=2002×100=200 分。

如此,你可以获得最高的总分 20+2001=21920+200-1=219

数据范围

对于 30%30\% 的测试点,保证 N<=15N<=15

对于 60%60\% 的测试点,保证 N<=100N<=100

对于所有测试点,保证 N1,000N \le 1,000;保证 0ai,bi1060 \le a_i,b_i \le 10^6