JOI 군은 점심으로 중국집에서 샤오롱바오를 먹기로 했다. 샤오롱바오는 속과 뜨거운 국물을 밀가루 피에 싼 요리로, 먹을 때 국물이 사방으로 튀기로 알려져 있다. JOI 군이 시킨 샤오롱바오 세트는 속과 국물이 서로 다른 \(N\)개로 이루어져 있다. \(N\)개의 샤오롱바오는 같은 간격으로 한 줄로 늘어서 있고, 차례로 \(1\)부터 \(N\)까지 번호가 붙어 있다. \(i\)번째와 \(j\)번째 사이의 거리는 절댓값 \(\lvert i-j \rvert\)이다. JOI 군은 샤오롱바오를 어떤 순서로 먹는다. 처음에는 모든 샤오롱바오의 맛있음이 \(0\)이다. \(i\)번째를 먹으면 국물이 튀어, 아직 먹지 않은 것 가운데 샤오롱바오 \(i\)로부터의 거리가 \(D_i\) 이하인 것에 국물이 묻는다. 국물이 묻은 샤오롱바오는 맛있음이 \(A_i\)만큼 늘어난다. 곧 \(i\)번째를 먹었을 때, \(j\)번째(\(1 \le j \le N\)이고 \(i-D_i \le j \le i+D_i\))가 아직 남아 있으면 \(j\)번째의 맛있음이 \(A_i\)만큼 늘어난다. JOI 군은 먹는 순서를 잘 정해, 먹는 샤오롱바오의 맛있음 합을 가장 크게 하고 싶다. 가장 좋은 순서로 먹었을 때 맛있음 합을 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(N\)
\(D_1\) \(D_2\) \(\cdots\) \(D_N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
- 입력은 \(3\)줄이다.
- 첫째 줄에 정수 \(N\)이 주어진다.
- 둘째 줄에 정수 \(N\)개 \(D_1, D_2, \ldots, D_N\)이 공백 하나로 구분되어 주어진다.
- 셋째 줄에 정수 \(N\)개 \(A_1, A_2, \ldots, A_N\)이 공백 하나로 구분되어 주어진다.
- \(1 \le N \le 100\)
- \(0 \le D_i \le 7\)
- \(0 \le A_i \le 1000\)
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에 JOI 군이 먹는 샤오롱바오의 맛있음 합의 최댓값을 출력한다.
\(5\)번째 \(\to\) \(3\)번째 \(\to\) \(1\)번째 \(\to\) \(2\)번째 \(\to\) \(4\)번째 순으로 먹으면 맛있음 합이 \(20\)이 된다. 합이 \(20\)을 넘는 먹는 방법은 없다.