CF351C.Jeff and Brackets

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 a__i mod n liters of ink on the i-th bracket of the sequence if he paints it opened and b__i 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.

杰夫喜欢规则括号序列。

今天，杰夫将取一张纸，写出一个长度为 $nm$ 的规则括号序列。我们从左到右将该序列中所有括号依次编号为 $0$ 到 $nm - 1$。杰夫知道：若他将第 $i$ 个括号涂成左括号（即开括号），则需消耗 $a_i \bmod n$ 升墨水；若涂成右括号（即闭括号），则需消耗 $b_i \bmod n$ 升墨水。

现已知序列 $a$、$b$ 以及整数 $n$、$m$。杰夫绘制一个长度为 $nm$ 的规则括号序列所需的最少墨水量是多少？

运算 $x \bmod y$ 表示 $x$ 除以 $y$ 所得的余数。

The first line contains two integers n and m (1 ≤ n ≤ 20; 1 ≤ m ≤ 107; m is even). The next line contains n integers: _a_0, _a_1, ..., a__n - 1 (1 ≤ a__i ≤ 10). The next line contains n integers: _b_0, _b_1, ..., b__n - 1 (1 ≤ b__i ≤ 10). The numbers are separated by spaces.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 20$；$1 \leq m \leq 10^7$；$m$ 为偶数）。
第二行包含 $n$ 个整数：$a_0, a_1, \dots, a_{n-1}$（$1 \leq a_i \leq 10$）。
第三行包含 $n$ 个整数：$b_0, b_1, \dots, b_{n-1}$（$1 \leq b_i \leq 10$）。
所有数字之间以空格分隔。

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

在一行中输出问题的答案——所需的最少墨水量（单位：升）。

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

在第一个测试用例中，最优序列为：()()()()()()，所需墨水升数为 12。