给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和长度为 $$$m$$$ 的数组 $$$b$$$,两者均仅由整数 $$$0$$$ 和 $$$1$$$ 组成。考虑一个大小为 $$$n \times m$$$ 的矩阵 $$$c_{i, j} = a_i \cdot b_j$$$ (即 $$$a_i$$$ 乘以 $$$b_j$$$)。很容易看出 $$$c$$$ 也仅由零和一组成。
$$$c$$$ 中有多少个大小(面积)为 $$$k$$$ 且仅由 1 个组成的子矩形?
子矩形是连续(后续)行段和连续(后续)列段的交集。 IE。考虑四个整数 $$$x_1, x_2, y_1, y_2$$$ ($$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le m$$$) 子矩形 $$$c[x_1 \dots x_2][y_1 \dots y_2]$$$ 是行的交集$$$x_1、x_1+1、x_1+2、\dots、x_2$$$ 和列 $$$y_1、y_1+1、y_1+2、\dots、y_2$$$。
子矩形的大小(面积)是其中的单元格总数。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n, m \leq 40\,000, 1 \leq k \leq n \cdot m$$$)、数组长度 $$$a$$$、数组长度 $$$b$$$ 以及所需的子矩形大小。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 1$$$),$$$a$$$ 的元素。
第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \leq b_i \leq 1$$$),$$$b$$$ 的元素。
输出
输出单个整数 — $$$c$$$ 的大小(面积)$$$k$$$ 只由 1 组成的子矩形的数量。
示例
输入 #1
3 3 2 1 0 1 1 1 1
输出 #1
4
输入 #2
3 5 4 1 1 1 1 1 1 1 1
输出 #2
14
注意
在第一个示例中,矩阵 $$$c$$$ 是:
有 $$$4$$$ 大小为 $$$2$$$ 的子矩形,其中仅包含以下子矩形:
在第二个示例中,矩阵 $$$c$$$ 为: