次のような動的計画法を考えます。

• $\mathrm{dp}_{i,j,k}$ : $a_1,\ldots,a_i$ から $j$ 個が選ばれていて、総和を $D$ で割った余りが $k$ であるようなときの総和の最大値(不可能なら $-1$ )

すると、答えは $\mathrm{dp}_{N,K,0}$ です。

遷移は、$a_i$ を選ぶ場合と選ばない場合を考えます。前者では $j$ が $1$ 増え、$k$ も$a_i$ の値に応じて変わります。後者では $j,k$ がともに変わりません。

より詳細には実装例を参考にしてください。

実装例 (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;
				
				//a_i を選ばない場合の遷移
				dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k]);
				
				//a_i を選ぶ場合の遷移
				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;
}

#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;
				
				//a_i を選ばない場合の遷移
				dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k]);
				
				//a_i を選ぶ場合の遷移
				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;
}