You have found yourself in a Halloween cave with ~N~ paths. You already know that with these ~N~ paths, you will end up in ~1~ of ~K~ endings numbered from ~1~ to ~K~, each one filled with some amount of candy! Of course, you want to get as much candy as possible, but after exploring ~2~ paths, spooky ghosts will chase you, and you'll need to get out of there as fast as possible! After grabbing candy by going through a path, you cannot visit the paths next to it, as the ghosts will block you from entering them. Can you figure out the maximum amount of candy you can get by going through at most ~2~ distinct paths that aren't next to each other?
Note: You do not necessarily have to go through ~2~ paths.
The first line will contain ~N~ ~(1 \leq N \leq 10^3)~, the number of paths, and ~K~ ~(1 \leq K \leq N)~, the number of endings. The next line will contain ~K~ integers ~a_i~ ~(1 \leq a_i \leq 1000)~, representing how much candy is in each path ending, respectively. The next line will contain ~N~ integers, ranging from ~1~ to ~K~ depending on which ending it leads to, or ~-1~ if it is a dead end.
Output ~1~ integer, the total number of candy you can get before the spooky ghosts come for you.
Sample Input 1
5 4 1 2 3 4 1 2 3 4 -1
Sample Output 1
Sample Explanation 1
You can go through the ~4~th entrance to get to the ~4~th ending, getting ~4~ candy. Then, you can go through the ~2~nd entrance to get another ~2~ candies, adding up to ~6~ in total.
Sample Input 2
8 3 91 59 1 2 1 2 -1 -1 -1 3 3
Sample Output 2
Sample Explanation 2
After exploring the first ending and getting ~91~ candies, the only way you can get more would be to go through the ~7~th or ~8~th entrances, getting ~1~ more candy. You cannot enter the second ending since you've entered the first one, and the only paths are next to the path of the first one.