题目描述
小 I 正在学习使用 Pytorch。这是一个非常热门的用于机器学习训练的 Python 库。
小 I 注意到,Pytorch 中对于张量运算有称作“广播”(broadcast)的机制。你可以认为张量是高维数组。对于一个 k 维张量 A,我们用长度为 k 的序列 (a1,a2,⋯,ak) 表示其各个维度的长度,也就是说 A 是一个 a1×a2×⋯×ak 的张量。
对于两个张量 A 和 B,设它们的维度分别为 (a1,a2,⋯,am) 和 (b1,b2,⋯,bn),称 A 和 B 是 可广播的,当且仅当以下性质成立:
- 对于任意整数 0≤i≤min,要么 a_{m-i} = b_{n-i},要么 a_{m-i} 和 b_{n-i} 中至少有一个是 1。
现在小 I 有两个张量,它们的维度分别是 (p_1,p_2,\cdots,p_m) 和 (q_1,q_2,\cdots,q_n),它们不一定是可广播的。
为此,小 I 可以使用 Pytorch 内置的函数进行若干次操作(可以不做操作),每次操作对序列 p 或 q 进行以下修改:
- 选择 p 或 q,在选定序列的任意一个位置插入一个 1。
小 I 想知道他最少要多少次操作才能让两个张量变为可广播的。
输入格式
从标准输入读入数据。
输入的第一行两个整数 m,n(1 \le m,n \le 2000) 表示两个张量的维度。
第二行 m 个整数 p_1,p_2,\cdots,p_m (1 \le p_i \le 2000) 描述第一个张量每个维度的长度。
第三行 n 个整数 q_1,q_2,\cdots,q_n (1 \le q_i \le 2000) 描述第二个张量每个维度的长度。
输出格式
输出到标准输出。
输入一行一个整数表示最少的插入 1 的数量使得两个张量变为可广播的。
样例
输入
4 2
2 1 3 2
4 2
输出
1
解释
在序列 q 的第二个位置之前插入一个 1(得到 4 1 2
),两个张量就会变为可广播的。