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. 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
'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
can gain from one spell.Subtasks
Subtask 1 (20%)
Subtask 2 (80%)
No further constraints.
Sample Input
7 5 3
2 5 2 8 1 4
2 6 5 7 4 7 4
Sample Output
18
Comments