#214533. [JOISC 2015] 防壁 / Walls

你获得了 JOI 社开发的一款电视游戏软件。这是一款相当不错的游戏，你每天都在愉快地游玩。

某天，游戏中出现了一个被称为“激光”的关卡。这个关卡极其困难，即使是优秀的玩家也只能以极低的概率通关。在多次挑战这个关卡的过程中，你意识到，如果能做出快速判断，或许就有机会通关，于是你开始思考编写程序来应对这个关卡。

“激光”关卡的舞台是一个设置了 个屏障的矩形区域。舞台被划分为 的正方形格子，每个格子由非负整数 表示为 。其中 是左下角的格子， 表示从 向右移动 格、向上移动 格到达的格子。

关卡开始时，敌人出现并发动攻击。敌人会连续发动 次攻击。第 次攻击时，敌人会从格子 向格子 发射激光。

每个屏障占据若干个 坐标相同的格子，形成一个宽度为 、高度为 1 的长方形。屏障 （）在关卡开始时占据从格子 到格子 的区域。在敌人第一次攻击前，以及每次攻击之间的间隙，你可以随时将任意一个屏障向左或向右移动一格。每次移动只能将一个屏障向右移动一格，或向左移动一格。

激光碰到屏障时威力会减弱。通过移动屏障，使得激光碰到所有屏障，从而将激光的威力降至最低。

你的目标是：在该关卡中，使屏障移动的总次数尽可能少。

题目

给定关卡开始时每个屏障的位置，以及每次敌人攻击的位置。当移动屏障使得激光碰到所有屏障时，求每个屏障移动次数的最小值。

从标准输入读取以下数据：

• 第一行包含两个整数 和 ，以空格分隔。这表示该关卡中有 个屏障，敌人将发动 次攻击。
• 接下来的 行中，第 行（）包含两个整数 和 ，以空格分隔。这表示在关卡开始时，屏障 被放置在从格子 到格子 的位置。
• 接下来的 行中，第 行（）包含一个整数 。这表示在第 次攻击时，敌人会从格子 向格子 立即发射激光。

向标准输出输出 行。第 行（）输出屏障 移动次数的最小值。

样例输入 1

4 4
0 3
4 4
2 7
8 11
6
4
3
8

样例输出 1

5
10
1
7

样例输入 2

7 11
12 39
22 23
5 38
6 47
10 43
0 50
18 46
38
19
15
1
12
29
29
0
6
40
6

样例输出 2

34
178
13
6
18
0
36

样例 1 解释

对于该输入，一种使屏障移动次数最小的移动方式如下：

• 在第 1 次攻击前，将屏障 1 向右移动 3 次，屏障 2 向右移动 2 次，屏障 3 保持不动，屏障 4 向左移动 2 次。
• 在第 2 次攻击前，屏障 1 保持不动，屏障 2 向左移动 2 次，屏障 3 保持不动，屏障 4 向左移动 2 次。
• 在第 3 次攻击前，屏障 1 保持不动，屏障 2 向左移动 1 次，屏障 3 保持不动，屏障 4 向左移动 1 次。
• 在第 4 次攻击前，屏障 1 向右移动 2 次，屏障 2 向右移动 5 次，屏障 3 向右移动 1 次，屏障 4 向右移动 2 次。

按照这种移动方式，屏障 1 移动 5 次，屏障 2 移动 10 次，屏障 3 移动 1 次，屏障 4 移动 7 次。

:::align{center}

图片来自于 LibreOJ。 :::

数据范围

所有输入数据满足以下条件：

• （）
• （）

子任务

子任务 1 [10 分]

子任务 2 [45 分]

• （）

子任务 3 [45 分]

无额外限制。

翻译由 Qwen3-235B 完成