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

3 0 20
* 2
!
+ 5

输出 1

4

说明 1

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

1. Bob 打出 + 5 牌，力量值变为 5。
2. Bob 打出 * 2 牌，力量值变为 10。
3. Bob 打出 ! 牌，怪物生命值变为 10。此时 Bob 手中已无卡牌，三张牌全部回到手中。
4. Bob 打出 ! 牌，怪物生命值变为 0，怪物被击败。

输入 2

1 0 1
!

输出 2

*

输入 3

1 1 1
+ 1

输出 3

*