```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var N, k, p int
	fmt.Fscan(in, &N, &k, &p)
	A := make([]int64, N)
	for i := 0; i < N; i++ {
		fmt.Fscan(in, &A[i])
	}
	prefix := make([]int64, N+1)
	for i := 1; i <= N; i++ {
		prefix[i] = prefix[i-1] + A[i-1]
	}
	const INF = 100000000
	dp := make([][]int, N+1)
	for i := range dp {
		dp[i] = make([]int, k+1)
		for j := range dp[i] {
			dp[i][j] = -INF
		}
	}
	dp[0][0] = 0
	for j := 1; j <= k; j++ {
		max_prev := make([]int, p)
		for rr := 0; rr < p; rr++ {
			max_prev[rr] = -INF
		}
		for next_i := j; next_i <= N; next_i++ {
			m := next_i - 1
			r := int(prefix[m] % int64(p))
			max_prev[r] = max(max_prev[r], dp[m][j-1])
			q := int(prefix[next_i] % int64(p))
			this_max := -INF
			for rr := 0; rr < p; rr++ {
				if max_prev[rr] != -INF {
					val := (q - rr + p) % p
					this_max = max(this_max, max_prev[rr]+val)
				}
			}
			dp[next_i][j] = this_max
		}
	}
	fmt.Println(dp[N][k])
}
```