[ARC175] B - Parenthesis Arrangement

B - Parenthesis Arrangement

Time Limit: 2 sec / Memory Limit: 1024 MB

题面

给定一个长度为的字符串，由字符(和)组成。记为中从左往右第个字符。

你可以以任意顺序零次或多次地执行以下两种操作：

• 选择一对整数，满足。交换和。此操作的花费为。

• 选择一个整数，满足。用(或)替换。此操作的花费为。

你的目标是使成为一个正确的括号序列。找到实现此目标所需的最小总成本。可以证明目标始终可以通过有限次操作实现。

什么是正确的括号序列？一个正确的括号序列是满足以下任一条件的字符串：

• 它是一个空字符串。
• 它是按照顺序连接(、、)而形成的，其中是一个正确的括号序列。
• 它是按照顺序连接和而形成的，其中和都是正确的括号序列。

限制条件

• 所有输入值均为整数。
• 是一个长度为的字符串，由字符(和)组成。

---

输入

输入数据遵循标准格式，格式如下:

输出

在一行中输出答案。

---

输入样例 1

3 3 2
)))(()

输出样例 1

5

这是一种操作方式：

• 交换和。变为))()()。花费为。
• 将替换为(。变为()()()，这是一个正确的括号序列。花费为。

在这种情况下，我们总共花费使成为一个正确的括号序列。无法在少于次操作中使成为一个正确的括号序列。

---

输入样例 2

1 175 1000000000
()

输出样例 2

0

给定的已经是一个正确的括号序列，因此不需要任何操作。

---

输入样例 3

7 2622 26092458
))()((((()()((

输出样例 3

52187538