Правильная скобочная последовательность — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы «1» и «+» между исходными символами. Например:
- скобочные последовательности «()()» и «(())» — правильные (из них можно получить выражения «(1)+(1)» и «((1+1)+1)»);
- скобочные последовательности «)(», «(» и «)» — неправильные.
Дана правильная скобочная последовательность. За один ход вы можете удалить пару соседних скобок такую, что левая скобка открывающая, а правая — закрывающая. Затем склеить полученные части, не изменяя порядка. Стоимость такого хода равна количеству скобок справа от правой скобки из этой пары.
Стоимость правильной скобочной последовательности равна наименьшей суммарной стоимости ходов, необходимых, чтобы сделать последовательность пустой.
На самом деле, никаких скобок вы не удаляете. Вместо этого вам дана правильная скобочная последовательность и целое число \(k\). Вы можете проделать следующее действие не больше \(k\) раз:
- вытащить скобку из последовательности и вставить ее в любую позицию (между двух скобок, в начало или в конец; возможно, туда же, где она и была).
После всех действий скобочная последовательность должна быть правильной. Какая наименьшая стоимость полученной правильной скобочной последовательности?