← 返回题目列表

Codeforces · 935/E

E. 法法与古代数学

中文机器翻译题面 查看原题

众所周知,古埃及人能够理解数学中的困难概念。古埃及数学家艾哈迈斯喜欢在纸莎草纸上书写一种算术表达式,他称之为艾哈迈斯算术表达式。

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。