All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Rhezo and Prime Problems
Tag(s):

Data Structures, Dynamic Programming, Easy, Number Theory

Problem
Editorial
Analytics

Rhezo and his friend Vanya love problem solving. They have a problem set containing $$N$$ problems, with points assigned to each. Rhezo wants to solve problems in such a way that he gets the maximum number of points. Rhezo has a weird habit of solving only prime number of consecutive problems, that is, if he solves $$X$$ consecutive problems from the problem set, then $$X$$ should be prime. Vanya has already solved all problems from the problem set and he wonders how much maximum points Rhezo can get. Vanya can answer this, but can you?

Input:

First line contains a single integer $$N$$, denoting the number of problems in the problem set. Next line contains $$N$$ space separated integers denoting the points assigned to the problems.

Output:

Print a single integer, the maximum points Rhezo can get.

Constraints:

$$1 \le N \le 5000$$

$$1 \le $$Points of Problems$$ \le 10^5$$

SAMPLE INPUT
4
8 1 3 7
SAMPLE OUTPUT
12
Explanation

Rhezo will solve problems $$1$$, $$2$$ and $$3$$, and will get $$12$$ points. Note that, he cannot solve all the problems because then he will solve $$4$$(non-prime) consecutive problems.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

ThoughtWorks

Challenge Name

ThoughtWorks Application Developer Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications