351_C. Jeff and Brackets_9665
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.
#include <bits/stdc++.h>
using namespace std;
const long long inft = 1000000009LL * 12324;
const int mod = 1000000007;
const int MAXN = 42;
int a[MAXN], b[MAXN];
long long M[MAXN][MAXN], A[MAXN][MAXN], T[MAXN][MAXN];
void solve() {
  int n, m;
  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]);
  int bil, mi, co;
  for (int i = 0; i < (MAXN); ++i)
    for (int j = 0; j < (MAXN); ++j) M[i][j] = inft;
  for (int i = 0; i < (MAXN); ++i)
    for (int j = 0; j < (MAXN); ++j) A[i][j] = (i == j ? 0 : inft);
  for (int mask = 0; mask < (1 << n); ++mask) {
    bil = 0;
    mi = 0;
    co = 0;
    for (int j = 0; j < (n); ++j) {
      if ((1 << j) & mask) {
        bil++;
        co += a[j];
      } else {
        bil--;
        co += b[j];
      }
      mi = min(mi, bil);
    }
    for (int bb = 0; bb < (MAXN); ++bb)
      if (bb + mi >= 0 && bb + bil < MAXN) {
        M[bb][bb + bil] = min(M[bb][bb + bil], 1LL * co);
      }
  }
  while (m) {
    if (m % 2) {
      for (int i = 0; i < (MAXN); ++i)
        for (int j = 0; j < (MAXN); ++j) T[i][j] = inft;
      for (int i = 0; i < (MAXN); ++i)
        for (int j = 0; j < (MAXN); ++j)
          for (int k = 0; k < (MAXN); ++k)
            T[i][j] = min(T[i][j], A[i][k] + M[k][j]);
      for (int i = 0; i < (MAXN); ++i)
        for (int j = 0; j < (MAXN); ++j) A[i][j] = T[i][j];
    }
    m /= 2;
    for (int i = 0; i < (MAXN); ++i)
      for (int j = 0; j < (MAXN); ++j) T[i][j] = inft;
    for (int i = 0; i < (MAXN); ++i)
      for (int j = 0; j < (MAXN); ++j)
        for (int k = 0; k < (MAXN); ++k)
          T[i][j] = min(T[i][j], M[i][k] + M[k][j]);
    for (int i = 0; i < (MAXN); ++i)
      for (int j = 0; j < (MAXN); ++j) M[i][j] = T[i][j];
  }
  printf("%d\n", (int)A[0][0]);
}
int main() {
  int te = 1;
  for (int ti = 0; ti < (te); ++ti) solve();
  return 0;
}

2 6
1 2
2 1
 1 10000000
2
3
 20 10000000
2 7 9 4 1 9 8 4 6 10 5 10 4 5 9 9 10 9 1 6
5 9 2 9 8 9 1 10 1 9 5 6 4 9 1 10 3 9 9 7
 20 10000000
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
 7 3952828
1 1 9 3 5 9 2
3 5 6 2 7 9 4
 2 1900670
10 3
9 6
 1 184
8
8
 3 184
3 2 8
3 9 2
 3 76
4 7 9
10 1 1
 5 114
7 5 8 10 10
2 7 9 4 5
 16 3273408
3 2 8 8 10 1 1 7 1 4 5 7 5 8 10 10
4 4 3 4 7 9 5 1 7 10 7 2 7 9 4 5
 20 10000000
7 4 3 4 7 7 6 5 4 6 5 8 3 5 3 8 4 3 4 8
7 6 3 2 2 10 4 3 5 7 9 9 8 5 4 9 4 3 3 4
 10 6007734
4 7 6 7 4 3 4 7 7 6
8 9 5 7 6 3 2 2 10 4
 11 4532614
7 3 4 1 8 3 5 2 8 10 9
6 10 3 7 5 1 1 8 4 9 7
 4 26
10 2 5 9
5 4 2 5
 9 7683580
4 6 8 5 10 6 3 4 7
6 7 3 10 3 10 1 4 10
 7 859320
10 1 4 9 2 5 5
5 10 3 6 6 5 10
 1 14
7
6
 3 3684044
8 6 4
3 1 2
 5 142
8 7 6 2 2
8 2 6 1 7
 6 17656
2 7 4 7 7 3
3 5 3 6 9 10
 20 10000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 20 10000000
6 7 3 9 10 10 1 9 4 6 8 5 10 6 3 4 7 8 6 6
7 4 7 2 7 3 10 10 6 7 3 10 3 10 1 4 10 10 7 3
 20 10000000
7 10 9 2 9 7 6 10 3 7 5 1 1 8 4 9 7 9 6 8
9 4 3 6 1 7 3 4 1 8 3 5 2 8 10 9 1 2 10 4
 3 98
6 1 9
10 2 4
 20 807878
9 4 2 5 2 7 9 3 4 4 9 2 8 3 8 9 5 7 4 7
8 4 8 7 10 4 10 6 8 1 7 9 3 10 2 2 6 7 3 9
 1 2
1
1
 20 10000000
10 3 2 6 2 3 9 2 8 4 4 4 3 4 7 9 5 1 7 10
9 6 2 8 3 2 8 10 6 3 2 8 8 10 1 1 7 1 4 5
 20 10000000
2 7 9 4 1 9 8 4 6 10 5 10 4 5 9 9 10 9 1 6
5 9 2 9 8 9 1 10 1 9 5 6 4 9 1 14 3 9 9 7
 7 3952828
1 1 9 3 5 9 2
3 3 6 2 7 9 4
 2 1900670
10 2
9 6
 1 98
8
8
 5 114
7 5 8 7 10
2 7 9 4 5
 16 3273408
3 2 8 8 10 1 1 7 1 4 5 7 5 8 10 11
4 4 3 4 7 9 5 1 7 10 7 2 7 9 4 5
 20 10000000
7 4 3 4 7 7 6 5 4 6 5 8 3 5 3 8 4 3 4 5
7 6 3 2 2 10 4 3 5 7 9 9 8 5 4 9 4 3 3 4
 10 6007734
4 7 6 7 4 3 4 7 7 6
8 9 3 7 6 3 2 2 10 4
 11 4532614
7 3 4 1 8 3 5 2 8 10 9
1 10 3 7 5 1 1 8 4 9 7
 9 7683580
4 6 8 5 10 2 3 4 7
6 7 3 10 3 10 1 4 10
 7 859320
10 1 4 9 2 1 5
5 10 3 6 6 5 10
 5 142
8 7 6 2 2
8 2 7 1 7
 6 17656
2 7 5 7 7 3
3 5 3 6 9 10
 3 98
10 1 9
10 2 4
 20 807878
9 4 2 5 2 7 9 3 4 4 9 2 8 3 8 9 5 7 4 7
8 4 8 7 10 4 10 6 8 1 7 9 3 10 2 2 6 7 3 13
 2 6
1 2
0 1
 1 10000000
1
3
 2 1900670
10 2
9 4
 1 70
8
8
 20 10000000
7 4 3 4 7 7 6 5 4 6 5 8 2 5 3 8 4 3 4 5
7 6 3 2 2 10 4 3 5 7 9 9 8 5 4 9 4 3 3 4
 11 4532614
7 3 4 1 8 3 5 2 8 17 9
1 10 3 7 5 1 1 8 4 9 7
 7 859320
8 1 4 9 2 1 5
5 10 3 6 6 5 10
 5 142
8 7 6 2 1
8 2 7 1 7
 3 98
10 1 2
10 2 4
 2 1900670
4 2
9 4
 20 10000000
7 4 3 4 7 7 6 5 4 6 5 9 2 5 3 8 4 3 4 5
7 6 3 2 2 10 4 3 5 7 9 9 8 5 4 9 4 3 3 4
 10 6007734
4 7 6 7 4 3 5 7 7 6
8 9 3 7 6 3 2 2 10 7
 11 4532614
7 3 4 1 8 3 5 2 8 17 9
1 10 3 7 5 1 1 8 7 9 7
 5 142
8 7 3 2 1
8 2 7 1 7
 3 98
10 1 2
10 2 2
 10 6007734
4 7 6 7 8 3 5 7 7 6
8 9 3 7 6 3 2 2 10 7
 5 142
12 7 3 2 1
8 2 7 1 7
 3 98
10 2 2
10 2 2
 10 6007734
4 7 6 7 8 3 5 7 8 6
8 9 3 7 6 3 2 2 10 7
 3 98
10 2 2
8 2 2
 7 3952828
1 1 9 3 5 9 2
3 6 6 2 7 9 4
 10 6007734
4 7 6 7 4 3 5 7 7 6
8 9 3 7 6 3 2 2 10 4
 7 859320
8 1 4 3 2 1 5
5 10 3 6 6 5 10
 2 1900670
4 4
9 4
 20 10000000
7 4 3 4 7 7 6 5 4 6 5 9 2 5 3 8 4 3 4 5
7 6 3 2 2 10 4 3 5 7 9 9 8 6 4 9 4 3 3 4
 11 4532614
7 3 4 1 8 3 5 2 8 17 9
1 10 3 10 5 1 1 8 7 9 7
 20 10000000
7 4 3 4 7 7 6 5 4 6 5 9 2 5 3 8 6 3 4 5
7 6 3 2 2 10 4 3 5 7 9 9 8 6 4 9 4 3 3 4

12
 25000000
 890000001
 2000000000
 106726356
 22808044
 1472
 1288
 684
 3021
 186584261
 880000001
 270348030
 201701323
 444
 303501412
 23201650
 91
 38682465
 2703
 459064
 200000000
 920000004
 780000008
 1127
 67053877
 2
 730000001
 890000001
 106726356
 20907375
 784
 2909
 186584261
 880000001
 258332562
 181304564
 272767092
 21483010
 2703
 459065
 1470
 67053881
 12
 20000000
 20907373
 560
 870000001
 185837178
 21483008
 2562
 1325
 15205360
 880000000
 270348031
 194902406
 2136
 1274
 282363499
 2211
 1372
 288371233
 1178
 106726356
 258332562
 21483008
 15205360
 880000001
 194902406
 880000001
