1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7  8 #define MAXN 105 9 #define MAXM 2010 #define GATE 1511 #define INF 0x3f3f3f3f12 int A[MAXN];13 int B[MAXN];14 int dp[MAXN*MAXN][MAXM];15 16 int main() {17     int l ,n;18     int i, j, k;19 20 #ifndef ONLINE_JUDGE21     freopen("data.in", "r", stdin);22 #endif23 24     while (scanf("%d %d", &l, &n) != EOF) {25         for (i=1; i<=l; ++i)26             scanf("%d", &A[i]);27         for (i=1; i<=l; ++i)28             scanf("%d", &B[i]);29         memset(dp, 0x3f, sizeof(dp));30         /*31         for (j=0; j<MAXM; ++j)32             dp[0][j] = INF;33         */34         dp[0][0] = 0;35         int p = 0;36         for (k=1; k<=n; ++k) {37             for (i=1; i<=l; ++i) {38                 ++p;39                 for (j=0; j<GATE; ++j) {40                     // no speed41                     if (j)42                         dp[p][j] = min(dp[p][j], dp[p-1][j-1]+A[i]);43                     // speed44                     if (j+5<GATE)45                         dp[p][j] = min(dp[p][j], dp[p-1][j+5]+B[i]);46                 }47                 // check the j=10 because, it can be turn from 1448                 dp[p][10] = min(dp[p][10], dp[p-1][14]+A[i]);49             }50         }51         int ans = INF;52         i = l*n;53         for (j=0; j<GATE; ++j)54             ans = min(ans, dp[i][j]);55         printf("%d\n", ans);56     }57 58     return 0;59 }