I - 塔 (Tower) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

The IOI Tower is an extremely tall tower equipped with a staircase for ascending. This staircase consists of 10^{100} steps, numbered sequentially from the bottom as step 0, step 1, and so on. JOI-kun is currently on step 0 and intends to climb the staircase. JOI-kun can ascend the staircase by taking the following 2 types of actions. Descending the staircase is not permitted.

  • Ascend 1 step. This action takes A seconds.
  • Jump from the current step to a step D steps above, skipping the steps in between. This action takes B seconds.

Currently, construction is ongoing at several locations on the staircase, and steps undergoing construction cannot be stepped on. Specifically, there are N ongoing constructions, and the i-th construction (1 \le i \le N) is being carried out at steps L_i, L_i + 1, \ldots, R_i.

The IOI Tower has Q rooms numbered from 1 to Q. One can enter room j (1 \le j \le Q) from step X_j of the staircase. Therefore, JOI-kun has decided to determine whether he can reach each room and, if possible, how many seconds it will take to reach there in the minimum time.

Given the information about JOI-kun, constructions, and rooms, create a program that determines whether JOI-kun can reach step X_j for each j (1 \le j \le Q) and, if possible, calculates the minimum time it takes.


Input

Read the following data from the standard input.

N Q
D A B
L_1 R_1
L_2 R_2
\vdots
L_N R_N
X_1
X_2
\vdots
X_Q

Output

Output Q lines to the standard output. On the j-th line (1 \le j \le Q), output the minimum number of seconds it takes if JOI-kun can reach step X_j; otherwise, output -1.

Constraints

  • 1 \le N \le 200\,000.
  • 1 \le Q \le 200\,000.
  • 1 \le D \le 10^{12}.
  • 1 \le A \le 1\,000\,000.
  • 1 \le B \le 1\,000\,000.
  • 1 \le L_i \le R_i \le 10^{12} (1 \le i \le N).
  • R_i + 1 < L_{i+1} (1 \le i \le N - 1).
  • 1 \le X_j \le 10^{12} (1 \le j \le Q).
  • Given values are all integers.

Subtasks

  1. (5 points) R_i \le 1\,000\,000 (1 \le i \le N), X_j \le 1\,000\,000 (1 \le j \le Q).
  2. (38 points) N \le 2\,000, Q \le 2\,000.
  3. (25 points) A = 1, B = D.
  4. (32 points) No additional constraints.

Sample Input 1

3 1
4 10 35
4 5
10 12
14 14
13

Sample Output 1

120

JOI-kun can reach the 13th step of the staircase in 120 seconds following the steps below:

  1. Ascend from step 0 to step 1. This action takes 10 seconds.
  2. Ascend from step 1 to step 2. This action takes 10 seconds.
  3. Ascend from step 2 to step 3. This action takes 10 seconds.
  4. Jump from step 3 to step 7, skipping the steps in between. This action takes 35 seconds.
  5. Ascend from step 7 to step 8. This action takes 10 seconds.
  6. Ascend from step 8 to step 9. This action takes 10 seconds.
  7. Jump from step 9 to step 13, skipping the steps in between. This action takes 35 seconds.

Since it's not possible to reach the 13th step of the staircase in less than 120 seconds, the output is 120.

This sample input satisfies the constraints of subtasks 1, 2, and 4.


Sample Input 2

5 10
10 1 9
7 11
25 32
37 38
43 44
50 52
6
12
18
24
30
36
42
48
54
60

Sample Output 2

6
11
17
22
-1
33
-1
44
-1
55

This sample input satisfies the constraints of subtasks 1, 2, and 4.

配点 : 100 点

問題文

IOI 塔は非常に高い塔であり,塔を上るための階段が備えられている.階段は 10^{100} 段あり,段には下から順に 0 段目,1 段目,\ldots と番号が付けられている.JOI 君は今 0 段目におり,階段を上ろうとしている.JOI 君は,以下の 2 種類の行動を行って階段を上ることができる.また,階段を下りることはできない.

  • 1 段上る.これにかかる時間は A 秒である.
  • 今いる段からその D 段上の段まで,間にある段を飛び越えて上る.これにかかる時間は B 秒である.

現在,階段のいくつかの場所では工事が行われており,工事が行われている段は踏むことができない.具体的には,N 個の工事が行われており,i 番目 (1 \leqq i \leqq N) の工事は L_i, L_i + 1, \ldots, R_i 段目で行われている.

IOI 塔には Q 個の部屋があり,1 から Q までの番号が付けられている.部屋 j (1 \leqq j \leqq Q) には階段の X_j 段目から入ることができる.そこで JOI 君は,それぞれの部屋にたどり着くことができるか,できる場合は最短で何秒かかるかを調べておくことにした.

JOI 君と工事と部屋の情報が与えられたとき,それぞれの j (1 \leqq j \leqq Q) について,JOI 君が X_j 段目にたどり着くことができるか判定し,できる場合は最短で何秒かかるかを求めるプログラムを作成せよ.


入力

入力は以下の形式で標準入力から与えられる.

N Q
D A B
L_1 R_1
L_2 R_2
\vdots
L_N R_N
X_1
X_2
\vdots
X_Q

出力

標準出力に Q 行出力せよ.j 行目 (1 \leqq j \leqq Q) には,JOI 君が X_j 段目にたどり着くことができる場合は最短でかかる時間の秒数を,できない場合は -1 を出力せよ.

制約

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq Q \leqq 200\,000.
  • 1 \leqq D \leqq 10^{12}.
  • 1 \leqq A \leqq 1\,000\,000.
  • 1 \leqq B \leqq 1\,000\,000.
  • 1 \leqq L_i \leqq R_i \leqq 10^{12} (1 \leqq i \leqq N).
  • R_i + 1 < L_{i+1} (1 \leqq i \leqq N - 1).
  • 1 \leqq X_j \leqq 10^{12} (1 \leqq j \leqq Q).
  • 入力される値はすべて整数である.

小課題

  1. (5 点) R_i \leqq 1\,000\,000 (1 \leqq i \leqq N),X_j \leqq 1\,000\,000 (1 \leqq j \leqq Q).
  2. (38 点) N \leqq 2\,000,Q \leqq 2\,000.
  3. (25 点) A = 1,B = D.
  4. (32 点) 追加の制約はない.

入力例 1

3 1
4 10 35
4 5
10 12
14 14
13

出力例 1

120

JOI 君は以下のような手順で階段の 13 段目に 120 秒でたどり着くことができる.

  1. 0 段目から 1 段目に上る.これにかかる時間は 10 秒である.
  2. 1 段目から 2 段目に上る.これにかかる時間は 10 秒である.
  3. 2 段目から 3 段目に上る.これにかかる時間は 10 秒である.
  4. 3 段目から 7 段目まで,間にある段を飛び越えて上る.これにかかる時間は 35 秒である.
  5. 7 段目から 8 段目に上る.これにかかる時間は 10 秒である.
  6. 8 段目から 9 段目に上る.これにかかる時間は 10 秒である.
  7. 9 段目から 13 段目まで,間にある段を飛び越えて上る.これにかかる時間は 35 秒である.

階段の 13 段目に 120 秒未満の時間でたどり着くことはできないので,120 を出力する.

この入力例は小課題 1, 2, 4 の制約を満たす.


入力例 2

5 10
10 1 9
7 11
25 32
37 38
43 44
50 52
6
12
18
24
30
36
42
48
54
60

出力例 2

6
11
17
22
-1
33
-1
44
-1
55

この入力例は小課題 1, 2, 4 の制約を満たす.


Source Name

JOI 2023/2024 春季トレーニング Contest Day3 問題3