LCC '21 Contest 1 J3 - Candy Collecting

View as PDF

Points: 5
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

You have found yourself in a Halloween cave with paths. You already know that with these paths, you will end up in of endings numbered from to , each one filled with some amount of candy! Of course, you want to get as much candy as possible, but after exploring 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 distinct paths that aren't next to each other?

Note: You do not necessarily have to go through paths.

Input Specification

The first line will contain , the number of paths, and , the number of endings. The next line will contain integers , representing how much candy is in each path ending, respectively. The next line will contain integers, ranging from to depending on which ending it leads to, or if it is a dead end.

Output Specification

Output 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

6

Sample Explanation 1

You can go through the th entrance to get to the th ending, getting candy. Then, you can go through the nd entrance to get another candies, adding up to in total.

Sample Input 2

8 3
91 59 1
2 1 2 -1 -1 -1 3 3

Sample Output 2

92

Sample Explanation 2

After exploring the first ending and getting candies, the only way you can get more would be to go through the th or th entrances, getting 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.