两条记录带分别用只含 0、1 的字符串 A、B 表示。

你要从每条带上各截取一个长度至少为 k 的连续区间，使两个区间包含的 1 的数量相同。两个区间不必等长，可以使用整条带。

求最大的共同数量。如果不存在满足要求的选择，输出 −1。

输入格式

本题只有一组输入数据。

第一行包含三个整数 n、m、k。第二行是长度为 n 的字符串 A，第三行是长度为 m 的字符串 B。

输出格式

输出最大的共同数量；无解时输出 −1。

数据范围

• 1 ≤ n,m ≤ 200000；
• 1 ≤ k ≤ min(n,m)；
• A、B 只包含字符 0、1。

样例 1

7 6 3
0011100
100101

3

说明：可以截取 A 的第 3 至 5 位与整条 B，两段都包含三个 1。

样例 2

4 5 3
1000
11111

-1

说明：A 的任意区间至多包含一个 1，而 B 中长度至少为 3 的区间至少包含三个 1。

下载样例数据