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