[ABC371] F - Takahashi in Narrow Road

F - Takahashi in Narrow Road

Time Limit: 3 sec / Memory Limit: 1024 MB

分数: 550 分

题面

有一条延伸东西方向的道路上有 个人。从称为原点的一个点，道路向东和向西无限延伸。

第 个人（）最初位于原点东 米处。

这些人可以沿着道路向东或向西移动。具体来说，他们可以执行以下任意次数的移动操作。

• 选择一个人。如果目的地没有其他人，将选择的人向东或向西移动 米。

他们总共有 个任务，第 个任务（）如下：

• 第 个人到达坐标 。

找到完成所有 个任务所需的最小总移动次数。

限制条件

• 所有输入值均为整数。

---

输入

从标准输入中按以下格式给出输入：

输出

输出答案。

---

输入样例 1

5
10 20 30 40 50
4
3 45
4 20
1 35
2 60

输出样例 1

239

人员的最佳移动顺序如下（人员的位置不一定按比例绘制）：

对于每个任务，人员的移动情况如下。

• 第 4 个人向东移动了 步，第 3 个人向东移动了 步。
• 第 2 个人向西移动了 步，第 3 个人向西移动了 步，第 4 个人向西移动了 步。
• 第 4 个人向东移动了 步，第 3 个人向东移动了 步，第 2 个人向东移动了 步，第 1 个人向东移动了 步。
• 第 5 个人向东移动了 步，第 4 个人向东移动了 步，第 3 个人向东移动了 步，第 2 个人向东移动了 步。

总移动次数为 。

你不能用总移动次数少于 完成所有任务，所以输出 239。

---

输入样例 2

8
0 1 2 3 4 5 6 100000000
6
1 100000000
8 0
1 100000000
8 4
1 100000000
5 21006578

输出样例 2

4294967297

请注意，有些人可能需要移动到原点的西边或距其东侧超过 米。

另外，答案可能超过 。

---

输入样例 3

12
1558 3536 3755 3881 4042 4657 5062 7558 7721 8330 8542 9845
8
9 1694
7 3296
12 5299
5 5195
5 5871
1 2491
8 1149
8 2996

输出样例 3

89644