P15614 [ICPC 2021 Jakarta R] Happy Travelling

A holiday is coming and Sam plans to visit his parents. There are $N$ cities numbered from $1$ to $N$. Sam lives in a campus dormitory in city $1$ while his parents live in city $N$. Sam already did some research on the cities. He assigns an integer $H_{i}$ to each city $i$ representing the "happiness value" he will get if he visits city $i$, including city $1$ and city $N$. As for the transportation, he found out that for every city $1 \leq i < N$, there is a one-way bus that starts at city $i$ and stops at each city from city $i + 1$ until city $i + T_{i}$; in other words, the bus will stop at each of the next $T_{i}$ cities. It is guaranteed that $i + T_{i} \leq N$. When Sam is at city $i < N$, he will board a bus that starts at city $i$ and alight at city $j$ where $j \in (i + 1, i + T_{i})$ while skipping all the stops between city $i$ and city $j$ (exclusive). Note that Sam cannot board a bus that does not start at city $i$ if he is at city $i$. Sam likes to be happy but he doesn't like being on a bus for a long time (he gets bored easily). Specifically, if he boards a bus that starts at city $i$ and alights at city $j$ (where $i < j$), then his happiness value will be decreased by the following. $$\left\lfloor \frac{j - i}{K} \right\rfloor \times D$$ Sam is busy preparing souvenirs for his parents and figuring out what to do when he gets there. So he needs your help computing the total maximum happiness value that he can get by carefully planning his journey from city $1$ to city $N$. For example, let $N = 6$, $K = 2$, $D = 1$, $H_{1..6} = \{8, -7, -8, 9, 0, 2\}$, and $T_{1..5} = \{5, 3, 3, 2, 1\}$. The maximum total happiness value that can be obtained from this example is $18$ as shown in the following plan. - Sam starts at city $1$. He obtains a happiness value of $H_{1} = 8$ at city $1$. - At city $1$, Sam boards the bus that can stop at any city in $[2, 6]$ and alights at city $4$. His happiness value is decreased by $\left\lfloor \frac{4-1}{2} \right\rfloor \times 1 = 1$ due to this bus trip. He obtains a happiness value of $H_{4} = 9$ at city $4$. - At city $4$, Sam boards the bus that can stop at any city in $[5, 6]$ and alights at city $5$. His happiness value is decreased by $\left\lfloor \frac{5-4}{2} \right\rfloor \times 1 = 0$ due to this bus trip. He obtains a happiness value of $H_{5} = 0$ at city $5$. - At city $5$, Sam boards the bus that can stop at any city in $[6, 6]$ and alights at city $6$. His happiness value is decreased by $\left\lfloor \frac{6-5}{2} \right\rfloor \times 1 = 0$ due to this bus trip. He obtains a happiness value of $H_{6} = 2$ at city $6$. In this plan, Sam boards a bus $3$ times with the total happiness value of $8 + (-1 + 9) + (0 + 0) + (0 + 2) = 18$. No other plan has a better total happiness value than this in this example.

Input begins with a line containing three integers $N$ $K$ $D$ ($2 \leq N \leq 100\,000$; $1 \leq K \leq N$; $0 \leq D \leq 10\,000$) representing the number of cities, and the parameter $K$ and $D$ as defined in the problem description, respectively. The second line contains $N$ integers $H_{i}$ ($-10\,000 \leq H_{i} \leq 10\,000$) representing the happiness value Sam will get if he visits city $i$. The third line contains $N-1$ integers $T_{i}$ ($1 \leq T_{i}$; $i + T_{i} \leq N$) for $1 \leq i < N$ representing the number of next contiguous cities in which the bus that starts at city $i$ will stop at.

Output contains an integer in a line representing the maximum total happiness value that can be obtained.

#### Explanation for the sample input/output #2 At city $1$, Sam boards the bus that can stop at any city in $[2, 6]$ and alights at city $3$. At city $3$, Sam boards the bus that can stop at any city in $[4, 8]$ and alights at city $8$. The total happiness value of this plan is $10 + (\left\lfloor \frac{3-1}{8} \right\rfloor \times 8 - 5) + (\left\lfloor \frac{8-3}{8} \right\rfloor \times 8 + 10) = 8 + (0 - 5) + (0 + 10) = 15$.