This is what I have done as it is correct but give tle :
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long
#define w(t) int t;cin>>t;while(t--)
#define mkarr(arr,n,type) type *arr=new type[n]
#define vi vector<int>
#define si set<int>
#define umii unordered_map<int,int>
#define umib unordered_map<int,bool>
#define mii map<int,int>
#define pii pair<int,int>
#define pqmax priority_queue<int>
#define pqmin priority_queue<int,vector<int> ,greater<int> >
#define qi queue<int>
#define sti stack<int>
#define li list<int>
#define fr(i,n) for(int i=0;i<n;i++)
#define db double
#define f first
#define s second
#define mkp make_pair
#define pb push_back
double PI=3.14159265358979323846264338327950L;
int32_t main()
{
fio;
w(t)
{
int n , m , k ;
cin>>n >> k >> m;
vector< int > v(n);
for(int i = 0; i<n ; i++){
cin>>v[i];
}
vector< vector< pair< int , int > >>dp(n , vector< pair< int , int > >(n));
for(int i = 0; i< n; i++){
for(int j = 0; j<n;j++){
dp[i][j] = {0,0} ;
}
}
for(int i = 0; i<n; i++){
dp[i][i] = {v[i] , 0};
}
for(int gap = 1 ; gap <n ; gap++){
for(int i = 0 , j = gap ; j<n ; i++ , j++){
int sum = INT_MAX;
int pos = INT_MAX;
for(int l =i; l<j ; l++){
if(dp[i][l].second + dp[l+1][j].second <= k){
if(sum > dp[i][l].first + dp[1+l][j].first) {
sum = dp[i][l].first + dp[1+l][j].first ; pos=dp[i][l].second + dp[1+l][j].second;
}
else if(sum == dp[i][l].first + dp[1+l][j].first) {
sum = dp[i][l].first + dp[1+l][j].first ; pos= min(pos , dp[i][l].second + dp[1+l][j].second); }
} }
if(dp[i+1][j-1].second + 1 <= k){
if(sum > dp[i+1][j-1].first + m) {
sum = dp[i+1][j-1].first + m; pos=dp[i+1][j-1].second + 1;
}
if(sum ==dp[i+1][j-1].first + m) {
sum = dp[i+1][j-1].first + m; pos= min(pos , dp[i+1][j-1].second + 1); } }
dp[i][j] = {sum , pos};
}
}
cout<<dp[0][n-1].first<<endl;
}return 0;
}