P15105 [ICPC 2025 LAC] Keep Fighting

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$），表示该卡牌提供的增量。 - **攻击**：该行包含字符 “!”（感叹号）。

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

### 样例 1 解释： 为了在 4 回合内击败怪物，Bob 可以按以下方式出牌： 1. Bob 打出 $+5$ 卡牌，因此他的攻击力变为 $5$。 2. Bob 打出 $*2$ 卡牌，因此他的攻击力变为 $10$。 3. Bob 打出 $!$ 卡牌，因此怪物的生命值变为 $10$。由于此时 Bob 手中没有卡牌，所有三张卡牌回到他手中。 4. Bob 打出 $!$ 卡牌，因此怪物的生命值变为 $0$，怪物被击败。 翻译由 DeepSeek V3 完成