#2432 술자리 계획하기

33  1 s   128 MB  

Description

한민이는 매일 매일 술자리를 즐기는 대학생입니다.
어느 날 한민이는 매일 즐기던 술자리에 체력의 한계를 느꼈고 앞으로는 3일 연속으로 술자리를 갖지 않기로 하였습니다. 하지만 연속된 N 일에 걸쳐서 약속을 잡은 상태였기 때문에 그중 3일 연속으로 술자리를 갖지 않으면서 최대한 즐겁게 술자리를 갖고자 합니다.
 
총 N 일에 대해 i번째 술자리를 참석하였을 경우 얻을 수 있는 즐거움을 ei 라 하면, 얻게 된 ei 의 합이 최대가 될 경우가 최대한 즐겁게 술자리를 가진 경우가 됩니다.
만약 연속된 5일 동안 1, 2, 3, 4, 5의 즐거움이 예상되는 약속을 잡았다고 가정합시다. 이 경우 1일차, 2일차 참석 후 3일차에 휴식을 하고 4일차, 5일차에 참석할 경우 (1 + 2 + 4 + 5 = 12)이 최대의 즐거움을 얻을 수 있습니다.
하지만 추가로, 한민이는 마지막 남은 양심을 걸고 시험 전날에는 술을 마시지 않기로 자신과 약속하였고 이 역시 지키려고 합니다. 만약 연속된 5일 동안 1, 2, 3, 4, 5의 즐거움이 예상되는 약속을 잡았으며 5일차에 시험이 있다고 합시다.
이 경우 2일차, 3일차 참석 후 4일차에 휴식을 하고 5일차에 참석하는 것(2 + 3 + 5 = 10)이 자신과 한 약속을 지키면서 최대의 즐거움을 얻을 수 있는 경우가 됩니다.

Input

입력은 총 세 줄로 구성됩니다. 첫째 줄에는 약속을 잡은 날의 수 N (1 ≤ N ≤ 1, 000)과 시험을 치는 날의 수 M (0 ≤ M ≤ N) 이 주어집니다.

둘째 줄에는 각 날의 즐거움이 예상되는 N 개의 정수 e1, e2, . . . , eN 이 주어지며, 마지막 줄에는 시험 날짜인 M 개의 서로 다른 정수 d1, d2, . . . , dM 이 주어집니다.

ei 는 100 이하의 양의 정수이며, di 는 N + 1이하의 양의 정수입니다.

입력에서 같은 줄에 있는 인접한 숫자들은 공백으로 구분됩니다.

Output

한민이가 얻을 수 있는 최대의 즐거움을 출력합니다.

Sample Input

Sample Output

10 3
4 2 9 2 6 3 9 9 4 7
1 2 7
42

Source

shake! 2015 본선