CF351C Jeff and Brackets

Jeff 喜欢正规括号序列。 今天，Jeff 要在一张纸上写出一个由 $nm$ 个括号组成的正规括号序列。我们将这个序列中的所有括号从左到右编号为 $0$ 到 $nm-1$。Jeff 知道，如果第 $i$ 个括号是左括号，他需要用掉 $a_{i \bmod n}$ 升墨水，如果是右括号则用掉 $b_{i \bmod n}$ 升墨水。 你有序列 $a$、$b$ 和数字 $n$、$m$。试问 Jeff 至少需要多少升墨水才能画出长度为 $nm$ 的正规括号序列？ 操作 $x \bmod y$ 表示 $x$ 除以 $y$ 的余数。

第一行包含两个整数 $n$ 和 $m$，满足 $1 \le n \le 20$，$1 \le m \le 10^{7}$，且 $m$ 为偶数。 第二行包含 $n$ 个整数，分别是 $a_0, a_1, \ldots, a_{n-1}$，每个 $1 \le a_i \le 10$。 第三行包含 $n$ 个整数，分别是 $b_0, b_1, \ldots, b_{n-1}$，每个 $1 \le b_i \le 10$。 数之间以空格隔开。

输出一行，表示画出正规括号序列所需的最少墨水量（升）。

在第一个测试样例中，最优的括号序列是 $()()()()()()$，所需的墨水量为 $12$ 升。 由 ChatGPT 5 翻译