DH的新手机

时间限制: 1000 ms 内存限制: 204800 kb
总通过人数: 0 总提交人数: 1

题目描述

DH最近买了个新手机,这个新手机的系统是一个新系统叫DS。这部手机安装了$n$个应用程序,每个程序都有它的图标。这些图标在不同的屏幕上,一个屏幕上有$k$个图标。第$1$个到第$k$个图标在第一个屏幕上,第$k+1$个到第$2k$个图标在第二个屏幕上,以此类推(最后一个屏幕可能会不足$k$个图标)。

开始时手机菜单显示的是第一个屏幕,想要启动第$t$个屏幕上的图标,DH需要先滑动屏幕$t-1$次,再点击该图标。

这个程序启动以后,将回到第一个屏幕,也就是说想要启动下一个应用程序又要从第一个屏幕开始先滑动再点击了。

应用程序的编号是从$1$到$n$的,我们现在知道刚开始每个应用程序所在的位置,不过因为DS系统的一个特殊功能,应用程序的位置是会随着DH的使用改变的。DS系统会把更常用的应用程序放在前边,更准确地说,当DH启动了一个应用程序后,这个应用程序会和它前边一位的应用程序交换位置,当然这两个相邻的程序可能在不同的屏幕上,这不影响,该交换还是会交换的,不过如果这个应用程序在最前边,就不会有交换顺序的事情发生了。

DH已经计划好了启动应用程序的顺序,他想知道这么做的话他需要做多少次操作(滑动屏幕和点击都算操作)。

需要注意的是一个应用程序可能会被启动多次。

输入

多组输入数据

对于每组数据,第一行有三个整数$n,m,k(1 \leq n,m,k \leq 10^5)$,分别表示DH新手机安装的应用程序数量,DH想要启动多少次应用程序,每个屏幕上的图标数量。

第二行有$n$个整数,$a_1,a_2,…,a_n$,表示刚开始时图标的顺序,$a_i$代表编号为$a_i$的程序在第$i$位。保证$a_1,a_2,…,a_n$为$1$到$n$的一个排列。

第三行有$m$个整数,$b_1,b_2,…,b_n$,表示DH计划启动应用程序的顺序,$b_i$代表编号DH计划启动的第$i$个程序是$b_i$。一个程序可能被启动多次。

输出

对于每组数据,输出一行,为一个整数,表示DH按他计划的启动应用程序的顺序需要进行的操作次数。

输入样例1

8 3 3
1 2 3 4 5 6 7 8
7 8 1

输出样例1

7

输入样例2

5 4 2
3 1 5 2 4
4 4 4 4

输出样例2

8

相关推荐