QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB
[+1]

# 7990. 广播

Statistics

题目描述

小 I 正在学习使用 Pytorch。这是一个非常热门的用于机器学习训练的 Python 库。

小 I 注意到,Pytorch 中对于张量运算有称作“广播”(broadcast)的机制。你可以认为张量是高维数组。对于一个 k 维张量 A,我们用长度为 k 的序列 (a1,a2,,ak) 表示其各个维度的长度,也就是说 A 是一个 a1×a2××ak 的张量。

对于两个张量 AB,设它们的维度分别为 (a1,a2,,am)(b1,b2,,bn),称 AB可广播的,当且仅当以下性质成立:

  • 对于任意整数 0imin,要么 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 内置的函数进行若干次操作(可以不做操作),每次操作对序列 pq 进行以下修改:

  • 选择 pq,在选定序列的任意一个位置插入一个 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),两个张量就会变为可广播的。