题目描述

乌龟棋的棋盘是一行 N 个格子，每个格子上一个分数（非负整数）。棋盘第 1 格是唯一的起点，第 N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中有 M 张爬行卡片，分成 4 种不同的类型（M 张卡片中不一定包含所有 4 种类型的卡片，见样例），每种类型的卡片上分别标有 1、2、3、4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。

游戏规则：

1. 玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

2. 乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。

3. 玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小珅想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小珅，他最多能得到多少分吗？

输入格式

第 1 行 2 个正整数 N 和 M，分别表示棋盘格子数和爬行卡片数。1≤N≤30，1≤M≤12。

第 2 行 N 个非负整数 a_1,a_2,……,a_N，其中 a_i 表示棋盘第 i 个格子上的分数。

第 3 行 M 个整数 b_1,b_2,……,b_M，表示 M 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 M 张爬行卡片，即 N−1=∑(i=1..M)b_i。

输出格式

输出只有 1 行，1 个整数，表示小珅最多能得到的分数。

9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1

73

2 1
965 916
1

1881

5 1
415 271 489 122 615
4

1030

数据范围与约定

1≤N≤30，1≤M≤12；卡片数字属于1至4，且所有卡片步数和为N-1。