Jeff 喜欢常规的括号序列。
今天 Jeff 将拿一张纸写出由 nm 个括号组成的常规括号序列。让我们从左到右对该序列的所有括号从 0 到 nm - 1 进行编号。杰夫知道,如果他将序列的第 i 个括号画成开放的,他将在该序列的第 i 个括号上花费 ai mod n 升的墨水,如果他将其画成封闭的,则将在该序列的第 i 个括号上花费 bi mod n 升的墨水。
你有序列 a、b 和数字 n、m。杰夫需要多少墨水才能绘制长度为 nm 的规则括号序列?
运算 x mod y 表示取数字 x 除以数字 y 后的余数。
输入
第一行包含两个整数 n 和 m(1 ≤ n ≤ 20;1 ≤ m ≤ 107;m 为偶数)。下一行包含 n 个整数:a0, a1, ..., an - 1 (1 ≤ ai ≤ 10)。下一行包含 n 个整数:b0, b1, ..., bn - 1 (1 ≤ bi ≤ 10)。数字之间用空格分隔。
输出
在一行中打印出问题的答案 — 所需的最小墨水量(以升为单位)。
示例
输入 #1
2 6 1 2 2 1
输出 #1
12
输入 #2
1 10000000 2 3
输出 #2
25000000
注意
在第一次测试中,最佳顺序是:()()()()()(),所需墨水升数为 12 升。