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.

Input Format

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 Format

Find the maximum revenue that can be generated. Check the sample output and question video.

Constraints

1 &lt;= M &lt;= 100000
1 &lt;= N &lt;= 50000
1 &lt;= Pi &lt;= M
1 &lt;= Ri &lt;= 100
1 &lt;= T

Example

Input

20
5
6 7 12 14 15
5 8 5 3 1
5

Output

2 Key Keyboard

Largest Square Sub-matrix With All 1's

Highway Billboard

Input Format

Output Format

Constraints

Example

Related Questions