## LCC/Moose '20 Contest 3 J4 - Chain Lightning

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

justinzhu is a wizard.

Not really, but he wishes he was. However in the game, Sorcery and Swords, he can achieve his dreams and play as a powerful lightning wizard. In Sorcery and Swords, monsters approach the player in a line. Each monster has a point value of . Additionally, each monster is separated from the previous by a distance of to lessen the chance that they will be wiped out by attacks with an area of effect. justinzhu has a chain lightning spell that allows him to take out at most monsters in succession, however, the distance of consecutive monsters must be less than or equal to .

Firing a chain lightning requires a lot of justinzhu's energy, so he would prefer to use the spell sparingly as he can allow the rest of his team to deal with the individual monsters. He has tasked you with finding out what the most efficient use of his spell would be.

Can you help him find the maximum amount of points that can be gained from one chain lightning spell?

#### Input Specification

The first line contains three space-separated integers

If , The next line contains integers, the distance between monsters, otherwise this line does not exist.

The next line contains integers, the point value assigned to each monster,

#### Output Specification

Output a single integer, the maximum amount of points that justinzhu can gain from one spell.

No further constraints.

#### Sample Input

7 5 3
2 5 2 8 1 4
2 6 5 7 4 7 4

#### Sample Output

18