题目背景

噜噜是一只热爱摇摆的生物。它根据一串表示情绪的 01 字符串 $s$ 来决定何时摇摆，每次摇摆的强度又取决于它当前的体力值。但是体力有限，每次大幅摇摆后都会消耗体力；当遇到休息时，体力又能恢复到初始水平。

题目描述

给定一个由字符 '0'（休息）和 '1'（摇摆）组成的字符串 $s$，以及一个非负整数初始体力值 $k$。噜噜按顺序处理 $s$ 中的每个字符：

• 遇到 '1' 时：

  1. 若此时体力已变为负，且再次遇到 '1'，则输出 gg 并停止处理。

  2. 若当前体力为 $m$，则本次摇摆包含

     $$2^0 + 2^1 + \dots + 2^m$$

     次基本动作；摇摆结束后，体力值减 $1$。

• 遇到 '0' 时： 休息一次，体力值立即恢复到初始值 $k$。

请计算噜噜在处理完整个 $s$ 序列后，所完成的基本摇摆动作总次数；或者输出 gg。

输入格式

• 第一行：字符串 $s$，长度 $1 \le |s| \le 10^5$，只包含字符 '0' 和 '1'。
• 第二行：整数 $k$，初始体力值，满足 $0 \le k \le 30$。

输出格式

• 若能完成所有动作，输出一个整数，表示总的基本摇摆动作次数；
• 若处理过程中体力变为负且再次遇到 '1' 时停止，输出字符串 gg。

示例输入输出

11101
2

18

1110110
1

gg

说明/提示

示例输入输出

说明/提示

• 对于示例 1，$k=2$ 且 $s=\texttt{"11101"}$：

  1. 第一次遇到 '1'：$m=2$，摇摆 $2^0+2^1+2^2=7$ 次，体力变为 $1$；
  2. 第二次遇到 '1'：$m=1$，摇摆 $2^0+2^1=3$ 次，体力变为 $0$；
  3. 第三次遇到 '1'：$m=0$，摇摆 $2^0=1$ 次，体力变为 $-1$；
  4. 遇到 '0'：休息，体力恢复至 $k=2$；
  5. 第四次遇到 '1'：$m=2$，摇摆 $2^0+2^1+2^2=7$ 次，体力变为 $1$；

  序列处理完毕，总计 $7+3+1+7=18$ 次基本动作。

• 示例 2 中，$k=1$：

  1. 前两次 '1' 摇摆后，体力依次变为 $0$ 和 $-1$；
  2. 第三次遇到 '1' 时因体力已为负，立即输出 gg。

数据范围

• $1 \le |s| \le 10^5$
• $0 \le k \le 30$
• 字符串 $s$ 只包含字符 '0' 和 '1'。

时间限制： 1 s 内存限制： 256 MB