ABC 281

void solve() {
    ll N, K, D;
    cin >> N >> K >> D;
    vll A(N + 1);
    rep(i, N) cin >> A[i + 1];

    // dp[i][j][r]: i 番目までの数字から j 個を選んだときの和を D
    // で割ったあまりが r のときの和の最大値
    vector<vvll> dp(N + 1, vvll(K + 1, vll(D, -INF)));
    dp[0][0][0] = 0;
    rep2(i, 1, N + 1) {
        rep(j, K + 1) {
            // i 番目の数字を使わない
            dp[i][j] = dp[i - 1][j];

            // i 番目の数字を使う
            if (j > 0) {
                rep(r, D) {
                    if (dp[i - 1][j - 1][r] < 0)
                        continue;
                    ll x = dp[i - 1][j - 1][r] + A[i];
                    chmax(dp[i][j][x % D], x);
                }
            }
        }
    }

    ll ans = dp[N][K][0];
    if (ans < 0)
        ans = -1;
    cout << ans << endl;
}