LCC/Moose '20 Contest 3 J4 - Chain Lightning

View as PDF

Submit solution

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

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, N monsters approach the player in a line. Each monster has a point value of p_i. Additionally, each monster is separated from the previous by a distance of a_i 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 K monsters in succession, however, the distance of consecutive monsters must be less than or equal to M.

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 N, M, K (1 \le K \le N \le 2 \cdot 10^5, 1 \le M \le 2 \cdot 10^5)

If N-1 > 0, The next line contains N-1 integers, the distance between monsters, a_1, a_2, ... , a_{N-1} (1 \le a_i \le 2 \cdot 10^5) otherwise this line does not exist.

The next line contains N integers, the point value assigned to each monster, p_1, p_2, ... , p_N (1 \le a_i \le 10^3)

Output Specification

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


Subtask 1 (20%)

N \le 1000

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



There are no comments at the moment.