C. Джефф и скобки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джефф любит правильные скобочные последовательности.

Сегодня Джефф собирается выписать на листок правильную скобочную последовательность, состоящую из nm скобок. Пронумеруем все скобки этой последовательности от 0 до nm - 1 слева направо. Джефф знает, что он потратит ai mod n литров чернил, если нарисует i-ую скобку последовательности открывающейся, и bi mod n литров чернил, если нарисует i-ую скобку закрывающейся.

Вам даны последовательности 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). Числа разделяются пробелами.

Выходные данные

В единственную строку выведите ответ на задачу — минимальный требуемый объем чернил в литрах.

Примеры
Входные данные
2 6
1 2
2 1
Выходные данные
12
Входные данные
1 10000000
2
3
Выходные данные
25000000
Примечание

В первом тесте оптимальная последовательность: ()()()()()(), требуемое количество литров чернил — 12.