You are given a sequence of
N natural numbers. All its continuous subsequences are considered, such that the sum of the elements of each of them is a multiple of
k = 43. Find among them a subsequence with the maximum sum, determine its length. If there are several such subsequences, in the answer indicate the number of elements of the shortest of them.
Input
Given two input files (
file A and
file B), each containing in the first line, the number of numbers
N (1<= N <= 10,000,000). Each of the following
N lines contains one natural number not exceeding 10 000.
An example of the organization of source data in the input file:
7
21
13
9
19
17
26
95
In this set, you can select the sequences
21+13+9 (the sum of
43) and
17+26 (the sum of
43 ). The shortest one,
17 + 26, is
2 long. For the specified, the program should output the number
2.
Warning: do not use brute-force algorithm to process file B, which calculates the sum of all possible options, as the program written in such an algorithm will run too long.