说明

Bob 正在玩一个需要击败怪物的卡牌游戏。在游戏开始前，Bob 的攻击力被设定为 $P$，怪物的生命值被设定为 $H$，并且 Bob 手上有 $N$ 张卡牌。

牌库中的每张卡牌属于以下类型之一：

• 乘法：此类卡牌上写有一个数字 $X$。使用它会使 Bob 当前的攻击力乘以 $X$。
• 加法：此类卡牌上也写有一个数字 $Y$。使用它会使 Bob 当前的攻击力增加 $Y$。
• 攻击：此类卡牌允许 Bob 攻击怪物。使用它会使怪物的当前生命值减少 Bob 当前的攻击力。

游戏按回合进行。在每个回合中，Bob 必须从他手中恰好打出一张卡牌，之后该卡牌被移到弃牌堆。如果在一个回合结束时 Bob 手中没有剩余卡牌，他会取回弃牌堆中的所有卡牌，并可以以任意顺序再次使用它们。

一旦怪物的生命值达到 $0$ 或更低，怪物就被击败。Bob 有可能击败怪物吗？如果可以，所需的最少回合数是多少？

输入格式

第一行包含三个整数 $N$（$1 \le N \le 50$）、$P$（$0 \le P \le 10^9$）和 $H$（$1 \le H \le 10^9$），分别表示牌库中的卡牌数量、Bob 的初始攻击力和怪物的初始生命值。

接下来的 $N$ 行描述每张卡牌。每行的内容取决于卡牌的类型，如下所示：

• 乘法：该行包含字符 “*”（星号）和一个整数 $X$（$1 \le X \le 10^9$），表示该卡牌提供的乘数。
• 加法：该行包含字符 “+”（加号）和一个整数 $Y$（$1 \le Y \le 10^9$），表示该卡牌提供的增量。
• 攻击：该行包含字符 “!”（感叹号）。

输出格式

输出一行，包含一个整数，表示击败怪物所需的最少回合数；或者，如果无法击败怪物，则输出字符 “*”（星号）。

3 0 20
* 2
!
+ 5

4

1 0 1
!

*

1 1 1
+ 1

*

提示

样例 1 解释：

为了在 4 回合内击败怪物，Bob 可以按以下方式出牌：

1. Bob 打出 $+5$ 卡牌，因此他的攻击力变为 $5$。
2. Bob 打出 $*2$ 卡牌，因此他的攻击力变为 $10$。
3. Bob 打出 $!$ 卡牌，因此怪物的生命值变为 $10$。由于此时 Bob 手中没有卡牌，所有三张卡牌回到他手中。
4. Bob 打出 $!$ 卡牌，因此怪物的生命值变为 $0$，怪物被击败。

翻译由 DeepSeek V3 完成