Description

For Xiao Ming's birthday, his father gave him a tortoise chess game as a present.

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

In the tortoise chess game, there are M crawling cards, divided into four different types (the M cards do not necessarily include all four 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 tortoise piece will move forward when the card is used. During the game, the player must select one unused crawling card from all available cards each time to control the tortoise piece to advance the corresponding number of squares. Each card can only be used once. The tortoise piece automatically earns the score of the starting square, and for each subsequent square it lands on, it earns the corresponding score. The player's final score is the sum of the scores of all squares the tortoise piece passes from the starting point to the destination.

Clearly, the order in which the crawling cards are used affects the final score. Xiao Ming wants to find an order of card usage that maximizes the final score.

Now, given the scores of each square on the board and all the crawling cards, can you tell Xiao Ming 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 board and the number of crawling cards, respectively.

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

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

The input data ensures that all M crawling cards are 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, with each type of the 4 crawling cards not exceeding 20 in quantity.

For 100% of the data: 1 ≤ N ≤ 350, 1 ≤ M ≤ 120, with each type of the 4 crawling cards not exceeding 40 in quantity; 0 ≤ ai ≤ 100, 1 ≤ i ≤ N; 1 ≤ bi ≤ 4, 1 ≤ i ≤ M.

Source

NOIP2010-S2