{"raw_statement":[{"iden":"statement","content":"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.\n\nEvery 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 ]$.\n\nGiven 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$.\n\nAn integer $N$ $(2 <= N <= 10^5)$, the amount of rooms. No input is provided for the last room since it's the room with the dragon.\n\nFollowed by a line with $N -1$ integers $(0 <= c_i <= 10^9)$, the amount of coins in the room.\n\nFollowed by another line with $N -1$ integers $(1 <= k_i <= N -1)$, how many rooms to the right Diego can move to. It is guaranteed that $i + k_i <= N$.\n\n2 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.\n\n"},{"iden":"input","content":"An integer $N$ $(2 <= N <= 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 <= c_i <= 10^9)$, the amount of coins in the room.Followed by another line with $N -1$ integers $(1 <= k_i <= N -1)$, how many rooms to the right Diego can move to. It is guaranteed that $i + k_i <= N$."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input5\n0 0 0 0\n4 3 2 1\nOutput0 8\nInput5\n0 0 0 0\n2 2 2 1\nOutput0 5\nInput7\n100 0 0 0 0 0\n2 2 2 2 2 1\nOutput100 13\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of rooms, with rooms indexed from $ 1 $ to $ N $.  \nLet $ C = (c_1, c_2, \\dots, c_{N-1}) \\in \\mathbb{Z}_{\\ge 0}^{N-1} $ be the coin values in rooms $ 1 $ to $ N-1 $ (room $ N $ has no coins).  \nLet $ K = (k_1, k_2, \\dots, k_{N-1}) \\in \\mathbb{Z}_{\\ge 1}^{N-1} $ be the maximum jump distances from each room $ i $, such that from room $ i $, Diego can move to any room $ j \\in [i+1, i + k_i] $, and $ i + k_i \\le N $.\n\n**Constraints**  \n1. $ 2 \\le N \\le 10^5 $  \n2. $ 0 \\le c_i \\le 10^9 $ for all $ i \\in \\{1, \\dots, N-1\\} $  \n3. $ 1 \\le k_i \\le N - 1 $ for all $ i \\in \\{1, \\dots, N-1\\} $  \n4. $ i + k_i \\le N $ for all $ i \\in \\{1, \\dots, N-1\\} $  \n\n**Objective**  \nDefine $ dp[i] $ as the maximum total coins collectable when reaching room $ i $, and $ ways[i] $ as the number of distinct paths to reach room $ i $ achieving $ dp[i] $, modulo $ 10^9 + 7 $.  \n\nInitialize:  \n- $ dp[1] = c_1 $, $ ways[1] = 1 $  \n- For $ i \\in \\{2, \\dots, N\\} $:  \n  $$\n  dp[i] = \\max_{\\substack{j < i \\\\ j + k_j \\ge i}} \\{ dp[j] \\} + \\begin{cases} c_i & \\text{if } i < N \\\\ 0 & \\text{if } i = N \\end{cases}\n  $$  \n  $$\n  ways[i] = \\sum_{\\substack{j < i \\\\ j + k_j \\ge i \\\\ dp[j] = dp[i] - \\text{coin}_i}} ways[j] \\mod (10^9 + 7)\n  $$  \n\nOutput: $ dp[N] $ and $ ways[N] \\mod (10^9 + 7) $","simple_statement":"Diego starts at room 1 and must reach room N.  \nIn each room i (1 ≤ i < N), he gets c_i coins and can jump to any room from i+1 to i+k_i.  \nFind the maximum coins he can collect by the time he reaches room N, and the number of different ways to achieve that maximum, modulo 10^9+7.","has_page_source":false}