Description
Due to its great contribution to the maintenance of world peace, Dzx was given an unlimited amount of candy free coupons to the candy company on May 23, 2010. On this day, Dzx can choose any of the N products from the candy company to take home and enjoy. Each of the N products of the candy company contains a different number of candies. Dzx hopes that the total number of candies in the products he chooses is an integer multiple of K, so that he can evenly distribute the candies to his partners who help him maintain world peace. Of course, on the basis of meeting this condition, the more the total number of candies, the better. How much candy can Dzx take away?
Note: Dzx can only take away the entire product of the candy company.
Format
Input
The first line contains two integers \(N(1 \leq N \leq 100)\) and \(K(1 \leq K \leq 100)\)
The following \(N\) lines have 1 integer in each line, indicating the number of candies contained in the product of the candy company, which does not exceed 1,000,000
Output
The maximum total number of candies that meet the requirements. If it cannot meet the requirement of multiples of \(K\), output 0
Sample
Input
5 7
1
2
3
4
5
Output
14
Sample Explanation
Dzx's choice is \(2+3+4+5=14\), so the total number of candies is a multiple of 7, and it is the most total choice.
Sample Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k,t;
int f[105][105];
int main() {
freopen("candy.in","r",stdin);
freopen("candy.out","w",stdout);
cin>>n>>k;
for(int i=1; i<=n; i++) {
cin>>t;
f[i][t%k]=t;//Store the total sugar with the same remainder.
for(int j=0; j<k; j++)
if(f[i-1][j])
f[i][(j+t)%k]=f[i-1][j]+t;
for(int j=0; j<k; j++)
f[i][j]=max(f[i][j],f[i-1][j]);
}
cout<<f[n][0]<<endl;//The result with a remainder of 0 is output. If there is no remainder with 0, then output 0 directly.
return 0;
}