Berland 州立大学 (BSU) 正在举办编程训练营。训练营将持续 $$$n$$$ 天,BSU 讲师计划在这些天里进行一些讲座。
新兵训练营的某些日子已计划为游览日,这些天不应举办任何讲座。为了确保参与者不会对学习编程感到太厌倦,每天的讲座次数不应超过$$$k_1$$$,并且每对连续天的讲座次数不应超过$$$k_2$$$。
你能计算一下训练营期间最多可以进行多少次讲座吗?形式上,找到最大整数$$$m$$$,以便可以选择$$$n$$$非负整数$$$c_1$$$、$$$c_2$$$、...、$$$c_n$$$(其中$$$c_i$$$是$$$i$$$当天举办的讲座数量),以便:
- $$$c_1 + c_2 + \dots + c_n = m$$$;
- 每个游览日 $$$d$$$, $$$c_d = 0$$$;
- 每天 $$$i$$$, $$$c_i \le k_1$$$;
- 对于每对连续天 $$$(i, i + 1)$$$, $$$c_i + c_{i + 1} \le k_2$$$。
请注意,可能有一些非游览日没有讲座(即,即使 $$$i$$$ 不是游览日,$$$c_i = 0$$$ 也可能是这样)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 50$$$) — 测试用例的数量。
然后是测试用例,每个测试用例由两行组成。第一行包含三个整数 $$$n$$$、$$$k_1$$$、$$$k_2$$$ ($$$1 \le n \le 5000$$$; $$$1 \le k_1 \le k_2 \le 200\,000$$$)。
第二行包含一个字符串$$$s$$$,恰好由$$$n$$$个字符组成,每个字符要么是0,要么是1。如果$$$s_i = 0$$$,则$$$i$$$日是游览日(因此当天应该没有讲座);如果 $$$s_i = 1$$$,则 $$$i$$$ 日不是游览日。
输出
对于每个测试用例,打印一个整数 - $$$m$$$ 的最大可能值(可以进行的讲座数量)。
示例
输入 #1
4 4 5 7 1011 4 4 10 0101 5 3 4 11011 6 4 6 011101
输出 #1
12 8 8 14