Subsequence with maximum sum
Problem
Given a sequence of
N integers. All its continuous subsequences starting from the first element of the sequence are considered. Find the maximum sum of a subsequence that is a multiple of
K, and the number of such subsequences.
Input
The first line contains two numbers: the number of numbers in the sequence
N (1 <= N <= 10
6) and the number
K ( 1 <= K <= 100). Next comes
N lines, one natural number per line. Each number does not exceed
10000.
Imprint
Print two space-separated numbers on the screen: the maximum sum of a subsequence that is a multiple of
K and the number of such subsequences
.
Examples
| # |
Input |
Output |
| 1 |
5 2
2
-2
2
-2
2 |
2 3 |