KUPC 的京都场地,综合研究大楼 7 号,每层都有一个公共休息室。 房间里配备了大白板、投影仪、屏幕、干净的桌椅,基本上任何人都可以自由使用。 有些人聚集在公共休息室参加编程比赛,7号楼的居民非常爱护这个房间。
今天在公共休息室,杏子和唯正在算命,以衡量他们的兼容性。 在这个算命中,长度 N,M 的两个序列 使用 A=(a_1,...,a_N) 和 将其放在 B=(b_1,...,b_M) 。 算命是按以下步骤进行的。
- Kyoko 和 Yui 之间的两个整数 决定 N,M 后, 做出Q 承诺。每个 Promise 都是两个整数 用 c_i,d_i 表示,序列 A 的 c_i 第一个数字和序列 B 的 d_i 表示数字必须相同。如果你违背了哪怕一个承诺,两个人的兼容性就会为零。
- 京子长了 N 序列 我想到了 A=(a_1,...,a_N) 。同样,Yui 的长度 我想到了 M 序列 我想到了 B=(b_1,...,b_M) 。
- 杏子和结衣各自按照自己想到的顺序在白板上重复写下了数字。更准确地说,i(≥1) 在第二篇文章中,Kyoko 写了一个数字序列。 A 的 ((i-1) mod N)+ 1 第一个数字,Yui 是一个数字序列。 同时在白板上写下第 B 的 ((i-1) mod M)+ 1 个数字。 指除以x mod y 是 x 从 y 后的余数。t 如果第二次书写时两人同时写出的数字不同,则相配算命结束,确定两人的相合度。 t 变为。
- 步骤 3 是 10^{10} 如果这种情况持续多次,结衣就会厌倦算命,两者之间的兼容性将降至0。
杏子刚刚和唯在一起。 我刚刚做出了 Q 承诺。杏子非常关心她即将进行的算命能得到的最大兼容性,所以公共休息室里的你决定帮助她计算最大兼容性。
入力形式
输入按以下格式给出。
N M Q c_1 d_1 … c_Q d_Q
出力形式
根据算命输出最大兼容性值。
制約
- 1 \leq N,M \leq 200
- 0 \leq Q \leq 200
- 1 \leq c_i \leq N
- 1 \leq d_i \leq M
- 相同的 Promise 在输入中不能出现多次。
- 所有输入值都是整数。
入出力例
入力例1
3 2 0
出力例1
4
入力例2
3 6 0
出力例2
6
入力例3
3 2 1 3 2
出力例3
3
入力例4
3 3 2 1 3 3 1
出力例4
2
入力例5
4 4 3 1 4 3 4 4 4
出力例5
3