题目描述

小明在一座古老神殿中探险，发现了一条由 $N$ 个石板铺成的走廊。每块石板上镶嵌着若干颗宝石（非负整数）。第 $1$ 块石板是起点，第 $N$ 块石板是终点。

小明拥有 $M$ 张传送符，分为 $4$ 种类型（不一定包含所有类型），每种类型上标有 $1,2,3,4$ 四个数字之一，表示使用后小明在走廊上向前跳跃相应的格数。每张传送符只能使用一次，且必须全部用完。

小明踏上第 $1$ 块石板时自动获得其上的宝石，之后每到达一块石板就获得该石板上的宝石。

请帮小明找出一种传送符的使用顺序，使得他收集到的宝石总数最多。

输入格式

每行中两个数之间用一个空格隔开。

第 $1$ 行 $2$ 个正整数 $N,M$，分别表示走廊石板数和传送符数。

第 $2$ 行 $N$ 个非负整数，$a_1,a_2,\ldots,a_N$，其中 $a_i$ 表示第 $i$ 块石板上的宝石数。

第 $3$ 行 $M$ 个整数，$b_1,b_2,\ldots,b_M$，表示每张传送符上的数字。

输入数据保证到达终点时刚好用完 $M$ 张传送符。

输出格式

一个整数，表示小明最多能收集到的宝石数。

样例

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

73

提示

数据范围

每个测试点 $1\mathrm{s}$。

对于 $30\%$ 的数据有 $1 \le N \le 30,1 \le M \le 12$。

对于 $50\%$ 的数据有 $1 \le N \le 120,1 \le M \le 50$，且 $4$ 种传送符每种不超过 $20$ 张。

对于 $100\%$ 的数据有 $1 \le N \le 350,1 \le M \le 120$，且 $4$ 种传送符每种不超过 $40$ 张；$0 \le a_i \le 100(1 \le i \le N),1 \le b_i \le 4(1 \le i \le M)$。