Highway Billboard
medium
1. You are given a number M representing length of highway(range). 2. You are given a number N representing number of bill boards. 3. You are given N space separated numbers representing (P)position of bill-boards. 4. You are given N space separated numbers representing (R)revenue corresponding to each (P)position. 5. You are given a number T such that bill-boards can only be placed after specific distance(T). 6. Find the maximum revenue that can be generated.
Constraints
1 <= M <= 100000 1 <= N <= 50000 1 <= Pi <= M 1 <= Ri <= 100 1 <= T
Format
Input
A number M(length of highway) A number N(number of bill boards) P1 ,P2 ,P3 ,P4 ,P5 .... Pn (placement of N bill-boards) R1 ,R2 ,R3 ,R4 ,R5 .... Rn (revenue from each bill-board) A number T (neccessary distance b/w two bill-board)
Output
Find the maximum revenue that can be generated. Check the sample output and question video.
Example
Sample Input
20
5
6 7 12 14 15
5 8 5 3 1
5
Sample Output
11