[ABC360] D - Ghost Ants

D - Ghost Ants

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 350 分

题面

在数轴上有 只蚂蚁，依次标记为 到 。蚂蚁 从坐标 处开始，并且面向正方向或负方向。最初，所有蚂蚁的坐标都不相同。每只蚂蚁面向的方向由长度为 的二进制字符串 表示，其中如果 为 0，则蚂蚁 面向负方向，如果 为 1，则蚂蚁 面向正方向。

当前时间设为 ，每只蚂蚁以单位时间内移动 单位的速度，在 单位时间内移动，直到时间为 时停止。如果多只蚂蚁到达相同坐标，它们会互相穿过而不改变方向或速度。在 单位时间后，所有蚂蚁停止。

找出这样的蚂蚁对数 ，满足 ，且蚂蚁 和蚂蚁 在此刻到达时间 之前互相穿过。

限制条件

• 是由 0 和 1 组成的长度为 的字符串。
• 、 和 都是整数。

---

输入

从标准输入中以以下格式给出：

...

输出

打印答案。

---

输入样例 1

6 3
101010
-5 -1 0 1 2 4

输出样例 1

5

以下五对蚂蚁会互相穿过：

• 蚂蚁 和蚂蚁 会在时间 时互相穿过。
• 蚂蚁 和蚂蚁 会在时间 时互相穿过。
• 蚂蚁 和蚂蚁 会在时间 时互相穿过。
• 蚂蚁 和蚂蚁 会在时间 时互相穿过。
• 蚂蚁 和蚂蚁 会在时间 时互相穿过。

没有其他蚂蚁互相穿过，因此输出为 。

---

输入样例 2

13 656320850
0100110011101
-900549713 -713494784 -713078652 -687818593 -517374932 -498415009 -472742091 -390030458 -379340552 -237481538 -44636942 352721061 695864366

输出样例 2

14