Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1210.

Problem Description

Given two arrays $a=[a_1,\dots,a_n]$ and $b=[b_1,\dots,b_n]$, each containing $n$ integers. You need to choose some indices $p_1< \cdots< p_k$ ($1\leq k\leq n$) such that the following conditions are satisfied:

• $1\leq p_i\leq n$ ($1\leq i\leq k$).
• $p_{i+1}\geq p_i+b_{p_i}$ ($1\leq i< k$).

Under these conditions, you need to maximize $\sum_{i=1}^k a_{p_i}$, i.e., maximize the sum of the values in array $a$ at the chosen indices.

Input Format

The first line contains a positive integer $n$, indicating the array length.

The second line contains $n$ positive integers $a_1,a_2,\dots,a_n$, representing array $a$.

The third line contains $n$ positive integers $b_1,b_2,\dots,b_n$, representing array $b$.

Output Format

One line containing an integer, representing the maximum possible sum of the values in array $a$ at the chosen indices, under the index constraints.

4
1 2 3 4
3 3 1 1

7

6
1 1 4 5 1 4
1 2 3 2 1 0

11

Hint

For $40\%$ of the testdata, it is guaranteed that $2\leq n\leq 10^3$.

For all testdata, it is guaranteed that $2\leq n\leq 10^5$, $0\leq a_i\leq 10^9$, and $0\leq b_i\leq n$.

Translated by ChatGPT 5