Джефф любит правильные скобочные последовательности.
Сегодня Джефф собирается выписать на листок правильную скобочную последовательность, состоящую из nm скобок. Пронумеруем все скобки этой последовательности от 0 до nm - 1 слева направо. Джефф знает, что он потратит ai mod n литров чернил, если нарисует i-ую скобку последовательности открывающейся, и bi mod n литров чернил, если нарисует i-ую скобку закрывающейся.
Вам даны последовательности a, b и числа n, m. Какое минимальное количество чернил понадобится Джеффу, чтобы нарисовать правильную скобочную последовательность длины nm?
Операция x mod y обозначает взятие остатка от деления числа x на число y.
Выходные данные
В единственную строку выведите ответ на задачу — минимальный требуемый объем чернил в литрах.
Примечание
В первом тесте оптимальная последовательность: ()()()()()(), требуемое количество литров чернил — 12.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 6
1 2
2 1
|
12
|
|
2
|
1 10000000
2
3
|
25000000
|