H-Infinite Array_第十八届浙大城市学院程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

You are given two arrays $a_{}$ and $b_{}$ , which has infinite length.
The first $n_{}$ elements of $a_{}$ is $a_1,a_2,...,a_n$ . If $k>n_{}$ , there is always $a_k=a_{k-n}$ .
The first $m_{}$ elements of $b_{}$ is $b_1,b_2,...,b_m$ . If $k>m_{}$ , there is always $b_k=b_{k-m}$ .
It is guaranteed that $gcd(n,m)=1_{}$ (gcd: the greatest common divisor).
You are given an integer $k_{}$ , you should find how many $t_{}$ satisfy $t\in[1,k],\ a_t>b_t$ .

输入描述:

The first line of the input contains three integer  ,  , meaning as shown above.
The second line contains  integers  .
The third line contains  integers  .

输出描述:

The output contains an integer, representing the answer.

示例1

输入

复制

3 5 9
2 4 10
3 5 8 1 4

输出

复制

说明

For the first example:
The array  is  .
The array  is  .
There are  positions where  .

示例2

输入

复制

5 6 1919810
1 2 3 4 5
1 1 4 5 1 4

输出

复制