Problem Statement

Maximum Treasure Score An explorer traverses an integer array A of length N . The explorer starts at index 0 and must finish at index N-1 . The value at every visited index, including the destination, is added to the score. From index i , the explorer may move forward by either: one position, to i+1 ; or a prime number of positions, to i+p , where p is prime. Moves that leave the array are not allowed. Find the maximum possible final score. Input The first line contains N . The second line contains N integers A[0] ... A[N-1] . Output Print the maximum score obtainable at index N-1 . Constraints 2 <= N <= 2000 -10^9 <= A[i] <= 10^9 A[0] = 0 The answer may require a 64-bit signed integer. Examples Input: 8 0 4 -10 6 -2 8 -3 5 Output: 23 An optimal path is 0 -> 1 -> 3 -> 5 -> 7 , using jumps of lengths 1, 2, 2, and 2. Input: 6 0 -5 10 -2 7 3 Output: 20 An optimal path is 0 -> 2 -> 4 -> 5 , using jumps of lengths 2, 2, and 1. Notes A prime jump is defined b