Description

On Xiaoming's birthday, his father gave him a turtle chess game as a present.

The turtle chessboard consists of a row of N squares, each with a score (a non-negative integer). The first square is the only starting point, and the Nth square is the destination. The game requires the player to control a turtle piece to move from the starting point to the destination.

There are M crawling cards in the turtle chess game, divided into 4 different types (the M cards may not include all 4 types, as shown in the sample). Each type of card is marked with one of the numbers 1, 2, 3, or 4, indicating the number of squares the turtle piece will move forward when the card is used. During the game, the player must select a previously unused crawling card from all available cards each time to control the turtle piece to advance the corresponding number of squares. Each card can only be used once. The turtle piece automatically earns the score of the starting square, and in subsequent moves, it earns the score of each square it lands on. The player's final score is the sum of the scores of all squares the turtle piece passes from the starting point to the destination.

Clearly, the order in which the crawling cards are used affects the final score. Xiaoming wants to find the optimal order of card usage to maximize the final score.

Now, given the scores of each square on the chessboard and all the crawling cards, can you tell Xiaoming the maximum score he can achieve?

Input Format

Each line of input contains numbers separated by a single space.

Line 1: Two positive integers N and M, representing the number of squares on the chessboard and the number of crawling cards, respectively.

Line 2: N non-negative integers, a1, a2, ..., aN, where ai represents the score of the i-th square on the chessboard.

Line 3: M integers, b1, b2, ..., bM, representing the numbers on the M crawling cards.

The input data guarantees that all M crawling cards will be used exactly when reaching the destination, i.e.,

Output Format

An integer representing the maximum score.

```input1 9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1 ``` ```output1 73 ``` ## Hint

【Data Range】

For 30% of the data: 1 ≤ N ≤ 30, 1 ≤ M ≤ 12.

For 50% of the data: 1 ≤ N ≤ 120, 1 ≤ M ≤ 50, and for each of the 4 types of crawling cards, the number of cards per type does not exceed 20.

For 100% of the data: 1 ≤ N ≤ 350, 1 ≤ M ≤ 120, and for each of the 4 types of crawling cards, the number of cards per type does not exceed 40; 0 ≤ a_i ≤ 100, 1 ≤ i ≤ N; 1 ≤ b_i ≤ 4, 1 ≤ i ≤ M.

Source

NOIP2010-S2