Problem: Time Warp

Want to try solving this problem? You can submit your code online if you log in or register.

Time Warp

Input File: standard input
Output File: standard output
Time Limit: 1 second
Memory Limit: 32 MB

You are a time traveller. You love concerts. Obviously, you combine these two hobbies.

Your time machine is powered by units called turbo warpers. When you use a y-year turbo warper, it propels you exactly y years into the past.

$\includegraphics[width=12cm]{samplewarp}$

The above diagram shows the effect of using a two-year turbo warper at the end of year 3. It's just a jump to the left. You then continue stepping to the right like normal. You can't use the warper again (but if you have another two-year turbo warper on hand, you can still use that one).

Further rules on time travel:

Your time machine is powered by lightning and dramatic clichés, so you can only use turbo warpers at the stroke of midnight on New Year's, to travel to previous years.
You cannot jump back any further than the start of year 1. If using a turbo warper would take you back further than that, it simply wouldn't work.
Due to mild interference between your time machine and the Mayan calendar, the world ends at the end of year X, where you are provided with the positive integer X. You can still use turbo warpers at the very end of year X.
You can use your turbo warpers in any order, and you don't need to use all your turbo warpers if you don't want to.

Some years were amazing years for concert goers: who can forget the first time Huey Lewis sang "The Power of Love"? Others were pretty terrible, like the time The Who were gatecrashed by an overdressed fellow wearing a celery stick. You've gone through every year in music history, and assigned it an integer audio score - the higher the score, the better the year was.

You wish to plot a path through time, whch must start at the beginning of year 1 and finish at the end of year X, maximising the total audio score of years you experience. Note that for each year you live through, its audio score is added to your total regardless of how many times you have experienced that year before.

Input

The first line of input will contain one line with two space-separated integers X and W.
The next X lines of input will contain one integer each, the ith of which represents the audio score of year i.
The next W lines of input will contain one integer each, describing the turbo warpers available to you (in no particular order).

Output

Output should consist of a single integer: the maximum possible total audio score you can achieve under the conditions described above.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

-4

Explanation

$\includegraphics[width=9cm]{warppath1}$

In the first sample case, you use all your available turbo warpers for a total audio score of:

6+9+6+9+0+8+7+8+9+0+8+7+-3 = 74

$\includegraphics[width=4.5cm]{warppath2}$

In the second sample case, you use only your 1-year turbo warpers for a total score of:

-5 + 2 + 2 + 2 + -5 = -4

Constraints & Subtasks

The following constraints apply to all subtasks:

1 ≤ X ≤ 100,000, where X is the year the world ends.
0 ≤ W ≤ 100, where W is the number of turbo warpers you have at your disposal.
-1,000 ≤ a_i ≤ 1,000, where a_i is the audio score of year i.
1 ≤ b_j ≤ X, where the jth turbo warper you own is a b_j-year turbo warper.

For each subtask, the following special constraints also apply:

For Subtask 1 (10 points), all turbo-warpers are one-year turbo-warpers (b_j = 1 for all j).
For Subtask 2 (20 points), you have exactly one turbo-warper (W = 1).
For Subtask 3 (35 points), the world lasts no longer than one millenium (X ≤ 1000).
For Subtask 4 (35 points), no special constraints apply.