Consider the following Dynamic Programming (DP) :

• \(\mathrm{dp}_{i,j,k}\) the maximum sum of \(j\) elements chosen out of \(a_1,\ldots,a_i\) such that the remainder when the sum is divided by \(D\) is \(k\) (or \(-1\) if it is impossible).

Then the answer is \(\mathrm{dp}_{N,K,0}\).

In a transition, we consider the cases where \(a_i\) is chosen and not. In the former case, \(j\) increases by \(1\), and \(k\) is also changed according to the value \(a_i\); in the latter, both \(j\) and \(k\) remains the same.

For more details, please refer to the sample code.

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    
	int N,K,D;
	cin>>N>>K>>D;
	
	vector<int> a(N);
	for(int i=0;i<N;i++)cin>>a[i];
	
	vector dp(N+1,vector(K+1,vector<long long>(D,-1)));
	dp[0][0][0] = 0;
	
	for(int i=0;i<N;i++){
		for(int j=0;j<K+1;j++){
			for(int k=0;k<D;k++){
				if(dp[i][j][k]==-1)continue;
				
				// transition when a_i isn't chosen
				dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k]);
				
				// transition when a_i is chosen
				if(j!=K){
					dp[i+1][j+1][(k+a[i])%D] = max(dp[i+1][j+1][(k+a[i])%D],dp[i][j][k] + a[i]);
				}
			}
		}
	}
	
	cout<<dp[N][K][0]<<endl;
	
	return 0;
}