샤오롱바오

시간 제한1초메모리 제한128 MB

요약

N개 만두를 먹는 순서를 정해 먹은 만두가 범위 안에 남은 만두에 더하는 보너스를 합해 전체 맛이 가장 커지도록 합니다.

문제

N개의 샤오롱바오가 일렬로 놓여 있다. 처음 맛은 모두 0이다. i번째를 먹으면 아직 남은 j번째 ( $|i-j| \le D_i$ )의 맛이 $A_i$ 만큼 증가한다. 먹는 순서를 정해 얻는 맛의 합을 최대화한다.

첫 줄에 $N$ ( $1 \le N \le 100$ ). 둘째 줄에 $D_i$ ( $0 \le D_i \le 7$ ), 셋째 줄에 $A_i$ ( $0 \le A_i \le 1000$ ).

최대 맛의 합을 출력한다.