Given a sequence of N natural numbers. It is known that the sum of all numbers in the sequence does not exceed 109. All its continuous subsequences are considered, in which the number of odd numbers is a multiple of K = 7. Find the largest sum of such a subsequence.
Input
The first line of the input contains a single number N (1 <= N <= 1 000 000) - number of numbers. Each of the following N lines contains one natural number not exceeding 1000.
Input
Print the answer to the problem
An example of the organization of source data in the input file (for К=4):
6
8
17
3
13
11
21
In this set, you can select the sequences 8+17+3+13+11 (sum 52) and 3+13+11+21 (sum 48).
Answer(for K = 4): 52.