406436: GYM102409 H Maximizing Coins

Diego is playing a very awesome RPG, in this game he is a knight and has to fight a dragon to the death, but before fighting the dragon he can buy some equipment which will make the fight easier. Help Diego get from the first room to the final room with as many coins as possible, and if there are many such answers tell Diego what in how many different ways he can reach the final room.

Every room is numbered from $$$1$$$ to $$$N$$$, they are sorted from left to right and can only move to the right (to rooms with bigger index). Also, every room $$$i$$$ has an amount of coins $$$c_i$$$, and from the room in position $$$i$$$, Diego can jump to any room with position $$$[i+1, i+k_i]$$$.

Given the $$$N$$$ rooms and their respective $$$k$$$ and $$$c$$$ values, tell Diego what is the maximum amount of coins he can get to the final room with and also in how many ways he can get there, since this number can be quite large print it modulo $$$10^9+7$$$.

An integer $$$N$$$ $$$(2 \le N \le 10^5)$$$, the amount of rooms. No input is provided for the last room since it's the room with the dragon.

Followed by a line with $$$N - 1$$$ integers $$$(0 \le c_i \le 10^9)$$$, the amount of coins in the room.

Followed by another line with $$$N - 1$$$ integers $$$(1 \le k_i \le N - 1)$$$, how many rooms to the right Diego can move to. It is guaranteed that $$$i+k_i \le N$$$.

2 integer numbers separated by a space, $$$C$$$ and $$$W$$$, the maximum amount of coins Diego can collect and all the ways he can collect them modulo $$$10^9+7$$$ respectively.

5
0 0 0 0
4 3 2 1

0 8

5
0 0 0 0
2 2 2 1

0 5

7
100 0 0 0 0 0
2 2 2 2 2 1

100 13