说明

大小王过生日的时候，他们的亲爸爸送给他们一副帝王棋当作生日礼物。饱含满满的父爱。

帝王棋的棋盘是一行N 个格子，每个格子上一个分数（非负整数）。棋盘第1 格是唯一的起点，第N 格是终点，游戏要求玩家控制一个帝王棋子从起点出发走到终点。1 2 3 4 5 …… N帝王棋中M 张爬行卡片，分成4 种不同的类型（M 张卡片中不一定包含所有4 种类型的卡片，见样例），每种类型的卡片上分别标有1、2、3、4 四个数字之一，表示使用这种卡片后，帝王棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制帝王棋子前进相应的格子数，每张卡片只能使用一次。游戏中，帝王棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是帝王棋子从起点到终点过程中到过的所有格子的分数总和。很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，大小王想要找到一种卡片使用顺序使得最终游戏得分最多。现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入格式

输入文件的每行中两个数之间用一个空格隔开。

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

第2 行N 个非负整数，a1,a2,……,aN，其中ai 表示棋盘第i个格子上的分数。

第3 行M 个整数，b1,b2, ……, bM，表示M张爬行卡片上的数字。

输入数据保证到达终点时刚好用光M张爬行卡片

输出格式

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

样例

13 4
32 37 75 16 64 33 79 97 22 2 99 100 41
4 2 2 4

326

提示

【数据范围】

对于30%的数据有1 ≤ N≤ 30，1 ≤M≤ 12。

对于50%的数据有1 ≤ N≤ 120，1 ≤M≤ 50，且4 种爬行卡片，每种卡片的张数不会超过20。

对于100%的数据有1 ≤ N≤ 350，1 ≤M≤ 120，且4 种爬行卡片，每种卡片的张数不会超过40；0 ≤ ai ≤ 100，1 ≤ i ≤ N；1 ≤ bi ≤ 4，1 ≤ i ≤M。