TOI16: Carte

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

typedef pair<int, int> pii;

const int N = 400;

int arr[N + 1];
pii dp[N + 1][N + 1];

int main(){

    int Q, limDish;
    scanf("%d%d", &Q, &limDish);
    int ans = 0;
    for(int l = 1; l <= N; ++l){
        dp[l][l] = pii(1, 1);
    }
    while(Q--){
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i){
            scanf("%d", &arr[i]);
        }
        for(int d = 2; d <= n; ++d){
            for(int l = 1; l <= n - d + 1; ++l){
                int r = l + d - 1;
                pii mn = pii(dp[l + 1][r].first + 1, 1);
                for(int i = l + 1; i <= r; ++i){
                    if(arr[l] == arr[i]){
                        pii newAns;
                        if(dp[i][r].second == limDish){
                            newAns = pii(dp[l + 1][i - 1].first + dp[i][r].first + 1, 1);
                        } else {
                            newAns = pii(dp[l + 1][i - 1].first + dp[i][r].first, dp[i][r].second + 1);
                        }
                        mn = min(mn, newAns);
                    }
                }
                dp[l][r] = mn;
            }
        }
        ans = max(ans, dp[1][n].first);
    }
    cout << ans;

    return 0;
}