众所周知,古埃及人能够理解数学中的困难概念。古埃及数学家艾哈迈斯喜欢在纸莎草纸上书写一种算术表达式,他称之为艾哈迈斯算术表达式。
Ahmes 算术表达式可以定义为:
- “d”是 Ahmes 算术表达式,其中 d 是一位正整数;
- “(E1 op E2)”是 Ahmes 算术表达式,其中 E1 和 E2 是有效的 Ahmes 算术表达式(不带空格),op 是加号 ( + ) 或减号 ( - )。
在去埃及的旅途中,法法发现了一张纸莎草纸,上面写着这些艾哈迈斯算术表达式之一。纸莎草纸非常古老,已经非常破旧。结果,所有运算符都被删除,只保留数字和括号。由于Fafa热爱数学,他决定挑战自己,完成以下任务:
给定原始表达式中加号和减号运算符的数量,将加号和减号运算符放在原来被删除的运算符的位置后,找出纸莎草纸上表达式的最大可能值。
输入
第一行包含一个字符串 E (1 ≤ |E| ≤ 104) — 一个有效的 Ahmes 算术表达式。所有运算符都被删除并替换为“?”。
第二行包含两个空格分隔的整数 P 和 M (0 ≤ min(P, M) ≤ 100) — 分别是加号和减号运算符的数量。
保证P + M = 被擦除的运算符的数量。
输出
打印包含问题答案的一行。
示例
输入 #1
(1?1) 1 0
输出 #1
2
输入 #2
(2?(1?2)) 1 1
输出 #2
1
输入 #3
((1?(5?7))?((6?2)?7)) 3 2
输出 #3
18
输入#4
((1?(5?7))?((6?2)?7)) 2 3
输出#4
16
注意
- 第一个样本将为 (1 + 1) = 2。
- 第二个样本将为 (2 + (1 - 2)) = 1。
- 第三个样本将为 ((1 - (5 - 7)) + ((6 + 2) + 7)) = 18。
- 第四个样本将为 ((1 + (5 + 7)) - ((6 - 2) - 7)) = 16。