#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[8][2] = {{1, 0}, {-1, 0}, {0, 1},  {0, -1},
                        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T max1(T a, T b, T c = -1234567, T d = -1234567) {
  T ans = a > b ? a : b;
  if (c != -1234567) ans = max1(ans, c);
  if (d != -1234567) ans = max1(ans, d);
  return ans;
}
template <class T>
inline T min1(T a, T b, T c = -1234567, T d = -1234567) {
  T ans = a < b ? a : b;
  if (c != -1234567) ans = min(ans, c);
  if (d != -1234567) ans = min(ans, d);
  return ans;
}
template <class T>
inline T gcd1(T a, T b) {
  if (a < b) swap(a, b);
  if (a % b == 0) return b;
  return gcd1(b, a % b);
}
template <class T>
inline T lb(T num) {
  return num & (-num);
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / abs1(a) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
inline int bitnum(unsigned long long nValue) {
  nValue = ((0xaaaaaaaaaaaaaaaaull & nValue) >> 1) +
           (0x5555555555555555ull & nValue);
  nValue = ((0xccccccccccccccccull & nValue) >> 2) +
           (0x3333333333333333ull & nValue);
  nValue = ((0xf0f0f0f0f0f0f0f0ull & nValue) >> 4) +
           (0x0f0f0f0f0f0f0f0full & nValue);
  nValue = ((0xff00ff00ff00ff00ull & nValue) >> 8) +
           (0x00ff00ff00ff00ffull & nValue);
  nValue = ((0xffff0000ffff0000ull & nValue) >> 16) +
           (0x0000ffff0000ffffull & nValue);
  nValue = ((0xffffffff00000000ull & nValue) >> 32) +
           (0x00000000ffffffffull & nValue);
  return nValue;
}
long long pow(long long n, long long m, long long mod = 0) {
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
int dp[25][50][100], ans[50];
int n, m;
int a[22], b[22];
inline void upd(int a, int &b) {
  if (b == -1 || a < b) b = a;
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", a + i);
  for (int i = 0; i < n; i++) scanf("%d", b + i);
  memset(dp, -1, sizeof(dp));
  dp[0][n * 2][n * 2] = 0;
  for (int i = 0; i < n; i++) {
    int now = i & 1, nxt = 1 - now;
    memset(dp[nxt], -1, sizeof(dp[nxt]));
    for (int j = n * 2 - i; j <= n * 2; j++)
      for (int k = j; k <= i + n * 2; k++)
        if (dp[now][j][k] != -1) {
          int temp = b[i] + dp[now][j][k];
          upd(temp, dp[nxt][min(j, k - 1)][k - 1]);
          temp = a[i] + dp[now][j][k];
          upd(temp, dp[nxt][j][k + 1]);
        }
  }
  memcpy(dp[0], dp[n & 1], sizeof(dp[0]));
  memset(dp[1], -1, sizeof(dp[1]));
  memset(ans, -1, sizeof(ans));
  ans[0] = 0;
  for (int ii = 0; m; m >>= 1, ii++) {
    if (m & 1) {
      int temp[50];
      memset(temp, -1, sizeof(temp));
      for (int i = 0; i < n * 2; i++)
        if (ans[i] != -1) {
          for (int j = n * 2 - i; j <= n * 2; j++)
            for (int k = j; k - n * 2 + i < n * 2 && k < n * 4; k++)
              if (dp[ii][j][k] != -1) {
                upd(ans[i] + dp[ii][j][k], temp[i + k - n * 2]);
              }
        }
      memcpy(ans, temp, sizeof(temp));
    }
    for (int i = 0; i <= n * 2; i++)
      for (int j = i; j < n * 4; j++)
        if (dp[ii][i][j] != -1)
          for (int i1 = max(0, n * 2 - j); i1 <= n * 2; i1++)
            for (int j11 = i1; j11 + j < n * 6 && j11 < n * 4; j11++)
              if (dp[ii][i1][j11] != -1) {
                upd(dp[ii][i][j] + dp[ii][i1][j11],
                    dp[ii + 1][min(i, j + i1 - n * 2)][j + j11 - n * 2]);
              }
  }
  cout << ans[0] << endl;
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

Jeff loves regular bracket sequences.

Today Jeff is going to take a piece of paper and write out the regular bracket sequence, consisting of nm brackets. Let's number all brackets of this sequence from 0 to nm - 1 from left to right. Jeff knows that he is going to spend ai mod n liters of ink on the i-th bracket of the sequence if he paints it opened and bi mod n liters if he paints it closed.

You've got sequences a, b and numbers n, m. What minimum amount of ink will Jeff need to paint a regular bracket sequence of length nm?

Operation x mod y means taking the remainder after dividing number x by number y.

Input

The first line contains two integers n and m (1 ≤ n ≤ 20; 1 ≤ m ≤ 107; m is even). The next line contains n integers: a0, a1, ..., an - 1 (1 ≤ ai ≤ 10). The next line contains n integers: b0, b1, ..., bn - 1 (1 ≤ bi ≤ 10). The numbers are separated by spaces.

Output

In a single line print the answer to the problem — the minimum required amount of ink in liters.

Examples

Input

2 6
1 2
2 1


Output

12


Input

1 10000000
2
3


Output

25000000

Note

In the first test the optimal sequence is: ()()()()()(), the required number of ink liters is 12.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[8][2] = {{1, 0}, {-1, 0}, {0, 1},  {0, -1},
                        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T max1(T a, T b, T c = -1234567, T d = -1234567) {
  T ans = a > b ? a : b;
  if (c != -1234567) ans = max1(ans, c);
  if (d != -1234567) ans = max1(ans, d);
  return ans;
}
template <class T>
inline T min1(T a, T b, T c = -1234567, T d = -1234567) {
  T ans = a < b ? a : b;
  if (c != -1234567) ans = min(ans, c);
  if (d != -1234567) ans = min(ans, d);
  return ans;
}
template <class T>
inline T gcd1(T a, T b) {
  if (a < b) swap(a, b);
  if (a % b == 0) return b;
  return gcd1(b, a % b);
}
template <class T>
inline T lb(T num) {
  return num & (-num);
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / abs1(a) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
inline int bitnum(unsigned long long nValue) {
  nValue = ((0xaaaaaaaaaaaaaaaaull & nValue) >> 1) +
           (0x5555555555555555ull & nValue);
  nValue = ((0xccccccccccccccccull & nValue) >> 2) +
           (0x3333333333333333ull & nValue);
  nValue = ((0xf0f0f0f0f0f0f0f0ull & nValue) >> 4) +
           (0x0f0f0f0f0f0f0f0full & nValue);
  nValue = ((0xff00ff00ff00ff00ull & nValue) >> 8) +
           (0x00ff00ff00ff00ffull & nValue);
  nValue = ((0xffff0000ffff0000ull & nValue) >> 16) +
           (0x0000ffff0000ffffull & nValue);
  nValue = ((0xffffffff00000000ull & nValue) >> 32) +
           (0x00000000ffffffffull & nValue);
  return nValue;
}
long long pow(long long n, long long m, long long mod = 0) {
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
int dp[25][50][100], ans[50];
int n, m;
int a[22], b[22];
inline void upd(int a, int &b) {
  if (b == -1 || a < b) b = a;
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", a + i);
  for (int i = 0; i < n; i++) scanf("%d", b + i);
  memset(dp, -1, sizeof(dp));
  dp[0][n * 2][n * 2] = 0;
  for (int i = 0; i < n; i++) {
    int now = i & 1, nxt = 1 - now;
    memset(dp[nxt], -1, sizeof(dp[nxt]));
    for (int j = n * 2 - i; j <= n * 2; j++)
      for (int k = j; k <= i + n * 2; k++)
        if (dp[now][j][k] != -1) {
          int temp = b[i] + dp[now][j][k];
          upd(temp, dp[nxt][min(j, k - 1)][k - 1]);
          temp = a[i] + dp[now][j][k];
          upd(temp, dp[nxt][j][k + 1]);
        }
  }
  memcpy(dp[0], dp[n & 1], sizeof(dp[0]));
  memset(dp[1], -1, sizeof(dp[1]));
  memset(ans, -1, sizeof(ans));
  ans[0] = 0;
  for (int ii = 0; m; m >>= 1, ii++) {
    if (m & 1) {
      int temp[50];
      memset(temp, -1, sizeof(temp));
      for (int i = 0; i < n * 2; i++)
        if (ans[i] != -1) {
          for (int j = n * 2 - i; j <= n * 2; j++)
            for (int k = j; k - n * 2 + i < n * 2 && k < n * 4; k++)
              if (dp[ii][j][k] != -1) {
                upd(ans[i] + dp[ii][j][k], temp[i + k - n * 2]);
              }
        }
      memcpy(ans, temp, sizeof(temp));
    }
    for (int i = 0; i <= n * 2; i++)
      for (int j = i; j < n * 4; j++)
        if (dp[ii][i][j] != -1)
          for (int i1 = max(0, n * 2 - j); i1 <= n * 2; i1++)
            for (int j11 = i1; j11 + j < n * 6 && j11 < n * 4; j11++)
              if (dp[ii][i1][j11] != -1) {
                upd(dp[ii][i][j] + dp[ii][i1][j11],
                    dp[ii + 1][min(i, j + i1 - n * 2)][j + j11 - n * 2]);
              }
  }
  cout << ans[0] << endl;
  return 0;
}

```