题目内容

小美是一名磁盘维修师，他的工作是检查和修复损坏的磁盘。为了提高工作效率，他使用了一种最短服务时间优先(SSTF)算法来安排他的磁盘读取请求。每当他收到一个需要读取某个磁道上的数据的请求，他就把它加入到一个队列中。然后，他按照SSTF算法的规则，选择一个最适合当前磁头位置的请求来执行。这样，他可以减少磁头移动的距离，节省时间和能源。

现在，小美想要知道，在一段时间内，他的磁头总共移动了多少个磁道。

给定 $0$ 时刻的磁头位置和速度，以及随后的一系列请求，请你帮助小美计算出这个数目。

SSTF算法的规则如下：每执行完一次磁盘读取后(读取时间忽略)，检查当前时刻及其之前到达的所有请求，服务距离当前磁道最近的请求。当有多个磁头距离当前值较近时，服务磁道号较小的请求。若当前时刻及其之前到达的所有请求都已经处理，磁头停留不动，等待下一个请求到来。

输入描述

输入第一行三个正整数 $n,m,k$ ，表示磁盘请求次数为 $n$ ，磁头每移动 $1$ 个磁道花费的时间为 $m$ ，磁头初始所在磁道号是 $k$ 。

输入第二行 $n$ 个正整数 $a_i$ ，表示第 $i$ 次请求的磁道号。

输入第三行 $n$ 个正整数 $t_i$ ，表示第 $i$ 次请求的到达时间，不保证该序列递增。

对于所有的数据： $1\le n\le 10^5，1\le a_i,t_i\le 10^9 , 1 \leq m \leq 100$ 。

输出描述

输出为一个整数，表示磁头移动的总磁道数。

样例

输入

5 1 5
3 4 1 8 5
10 4 9 7 8

输出

12

样例解释

0时刻进入等待状态至4时刻 当前请求队列为(数字代表磁道号):{ 4 }

4 时刻 磁头从5号磁道 移动到 4号磁道 ,5时刻到达, 当前移动长度为1

5时刻进入等待状态至7时刻 当前请求队列为(数字代表磁道号):{ 8 }

7 时刻 磁头从4号磁道 移动到 8号磁道 ,11时刻到达, 当前移动长度为5 当前请求队列为(数字代表磁道号):{ 1 3 5 }

11 时刻 磁头从8号磁道 移动到 5号磁道 ,14时刻到达, 当前移动长度为8 当前请求队列为(数字代表磁道号):{ 1 3 }

14 时刻 磁头从5号磁道 移动到 3号磁道 ,16时刻到达, 当前移动长度为10 当前请求队列为(数字代表磁道号):{ 1 }

16 时刻 磁头从3号磁道 移动到 1号磁道 ,18时刻到达, 当前移动长度为12

总移动长度为12

题目思路:模拟 + multiset

cpp代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
#define int long long