#include <bits/stdc++.h>
#include "nile.h"
#define fi first
#define se second
#define ll long long
#define pb push_back
using namespace std;
const ll INF=1e18+5;
const int N=2005;
ll dp[N][N];
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
int Q=(int)e.size(), n=(int)w.size();
vector<array<int,3>> ar(n);
for(int i=0; i<n; i++){
ar[i][0]=w[i];
ar[i][1]=a[i];
ar[i][2]=b[i];
}
sort(ar.begin(),ar.end());
vector<long long> atb(Q, 0);
for(int q=0; q<Q; q++){
int d=e[q];
for(int i=0; i<n; i++) dp[i][i]=ar[i][1];
for(int i=0; i<n-1; i++){
if(ar[i+1][0]-ar[i][0]<=d) dp[i][i+1]=ar[i][2]+ar[i+1][2];
else dp[i][i+1]=ar[i][1]+ar[i+1][1];
}
for(int di=2; di<n; di++){
for(int l=0; l+di<n; l++){
int r=l+di;
dp[l][r]=INF;
dp[l][r]=min(dp[l][r],dp[l][r-1]+ar[r][1]);
dp[l][r]=min(dp[l][r],dp[l+1][r]+ar[l][1]);
dp[l][r]=min(dp[l][r],dp[l][r-2]+dp[r-1][r]);
dp[l][r]=min(dp[l][r],dp[l+2][r]+dp[l][l+1]);
cout<<l<<' '<<r<<' '<<dp[l][r]<<'\n';
}
}
atb[q]=dp[0][n-1];
}
return atb;
}
/*
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5
9
1
*/
