题目描述

给定两个长度为 $n$ 的二进制字符串 $A$ 和 $B$（字符只包含 0 和 1）。有两个人分别在字符串 $A$ 和 $B$ 对应的位置上行走，位置编号为整数 $0,1,2,\dots,n,n+1$，其中 $1\ldots n$ 对应字符串的字符位置，$0$ 与 $n+1$ 为虚拟的起点和终点。

行走规则

• 两人不能同时行动，且只能向前走。
• 在字符串 $A$ 上的那个人每一步可以向前移动的步幅为任意整数 $x$，满足 $L_1 \le x \le R_1$。
• 在字符串 $B$ 上的那个人每一步可以向前移动的步幅为任意整数 $y$，满足 $L_2 \le y \le R_2$。
• 两个人只能位于字符为 1 的格子（即位置 $i$ 若对应字符串字符为 1 才能停留）。
• 两个人的目标是从位置 $0$ 共同移动到位置 $n+1$（每一次行动可以选择移动其中一人一次）。
• 在任意时刻，两个行者之间的距离差（即位置之差的绝对值）不得超过常数 $D$。

求有多少个位置（在 $1\ldots n$ 中的字符 1）是有可能被两个人经过的。

输入格式

第一行输入 $6$ 个整数 $n, L_1, R_1, L_2, R_2, D$。

随后两行，每行输入一个长度为 $n$ 的 $01$ 字符串，分别表示字符串 $A$ 和 $B$。

输出格式

输出到文件 walk.out 中。

输出一个整数，表示答案（可被两个人经过的 1 的位置个数）。

样例输入 1

7 4 6 1 2 2
0101010
1110111

样例输出 1

7

样例输入 2

60 4 41 25 54 16
101000110011010010000111110100001000101100111010110011001100
010000011001110100010100011011000001001000110011011010110010

样例输出 2

21

说明

对于 $100\%$ 的数据，$1\le n\le 2\times 10^3,1\le L_1\le R_1\le n+1,1\le L_2\le R_2\le n+1,1\le D\le n+1$。

特殊性质 A：$L_1 = L_2 = 1,R_1 = R_2 = n + 1,D = n + 1$。

特殊性质 B：$L_1 = L_2 = 1,R_1 = R_2 = n + 1$。