← 返回题目列表

AtCoder · kupc2014_c

C. 算命

中文机器翻译题面 查看原题

KUPC 的京都场地,综合研究大楼 7 号,每层都有一个公共休息室。 房间里配备了大白板、投影仪、屏幕、干净的桌椅,基本上任何人都可以自由使用。 有些人聚集在公共休息室参加编程比赛,7号楼的居民非常爱护这个房间。

今天在公共休息室,杏子和唯正在算命,以衡量他们的兼容性。 在这个算命中,长度 N,M 的两个序列 使用 A=(a_1,...,a_N) 和 将其放在 B=(b_1,...,b_M) 。 算命是按以下步骤进行的。

  1. Kyoko 和 Yui 之间的两个整数 决定 N,M 后, 做出Q 承诺。每个 Promise 都是两个整数 用 c_i,d_i 表示,序列 A 的 c_i 第一个数字和序列 B 的 d_i 表示数字必须相同。如果你违背了哪怕一个承诺,两个人的兼容性就会为零。
  2. 京子长了 N 序列 我想到了 A=(a_1,...,a_N) 。同样,Yui 的长度 我想到了 M 序列 我想到了 B=(b_1,...,b_M) 。
  3. 杏子和结衣各自按照自己想到的顺序在白板上重复写下了数字。更准确地说,i(≥1) 在第二篇文章中,Kyoko 写了一个数字序列。 A 的 ((i-1) mod N)+ 1 第一个数字,Yui 是一个数字序列。 同时在白板上写下第 B 的 ((i-1) mod M)+ 1 个数字。 指除以x mod y 是 x 从 y 后的余数。t 如果第二次书写时两人同时写出的数字不同,则相配算命结束,确定两人的相合度。 t 变为。
  4. 步骤 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