#include #include #include int min(int a, int b) { return a>b?b:a; } void getArray(int index, int *array){ int num; int cnt = 0; memset(array, 0, index); while(cnt < index){ scanf("%d",&num); char c=getchar(); array[cnt++]=num; if(c =='\n'){ break; } } } void findMinTime(int N, int C, int V, int *S, int *T, int *Y,int *M){ int **dp; int ans = 1000; dp = (int **)malloc(sizeof(int * ) * V); for(int i = 0; i < V; i++){ dp[i] = (int *)malloc(sizeof(int) * (C + 1)); } for(int i = 0; i < V; i++){ for(int j = 0; j < (C + 1); j++){ dp[i][j] = 1000; } } dp[0][C] = 0; for(int i = 0; i < N; ++i){ for(int j = C ; j >= 0; --j){ if(dp[i][j] != 1000){ for (int k = 0; k < V ; ++k){ if(i == S[k] - 1 && j - Y[k] >= 0){ dp[T[k] - 1][j - Y[k]] = min(dp[i][j] + M[k], dp[T[k] - 1][j - Y[k]]); } } } } } for(int j = 0; j < (C + 1); j++) { ans = min(ans, dp[N-1][j]); } if(ans == 1000){ ans = -1; } printf("%d ", ans); } int main(){ int N,C,V; int S[1500], T[1500], Y[1500], M[1500]; scanf("%d", &N); scanf("%d", &C); scanf("%d", &V); getArray(V, S); getArray(V, T); getArray(V, Y); getArray(V, M); findMinTime(N,C,V,S,T,Y,M); }