{"problem":{"name":"[JOIST 2024] 塔楼 / Tower","description":{"content":"IOI Tower 是一座极其高的塔楼，配备了一条用于上升的楼梯。这个楼梯由 $10^{100}$ 个台阶组成，从底部开始依次编号为第 $0$ 级、第 $1$ 级，依此类推。JOI 君目前在第 $0$ 级，并打算爬楼梯。JOI 君可以通过以下两种方式上楼，禁止下楼。 - 上升 $1$ 级。这个动作需要 $A$ 秒。 - 从当前级别跳到上方 $D$ 级，跳过中间的台阶。这个动作需要 $B$ 秒。 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10438"},"statements":[{"statement_type":"Markdown","content":"IOI Tower 是一座极其高的塔楼，配备了一条用于上升的楼梯。这个楼梯由 $10^{100}$ 个台阶组成，从底部开始依次编号为第 $0$ 级、第 $1$ 级，依此类推。JOI 君目前在第 $0$ 级，并打算爬楼梯。JOI 君可以通过以下两种方式上楼，禁止下楼。\n\n- 上升 $1$ 级。这个动作需要 $A$ 秒。\n- 从当前级别跳到上方 $D$ 级，跳过中间的台阶。这个动作需要 $B$ 秒。\n\n目前，楼梯的几个位置正在进行施工，正在施工的台阶不能踩上去。具体来说，有 $N$ 处正在进行施工，第 $i$ 处施工（$1 \\leq i \\leq N$）正在进行的台阶为 $L_i$ 到 $R_i$。\n\nIOI Tower 有 $Q$ 个房间，编号从 $1$ 到 $Q$。人们可以从楼梯的第 $X_j$ 级进入第 $j$ 个房间（$1 \\leq j \\leq Q$）。因此，JOI 君决定确定他是否可以到达每个房间，如果可能的话，以最短时间需要多少秒到达。\n\n给出关于 JOI 君、施工和房间的信息，创建一个程序，确定 JOI 君是否可以到达第 $j$ 个房间（$1 \\leq j \\leq Q$），如果可能的话，计算需要的最短时间。\n\n## Input\n\n从标准输入读取以下数据。\n\n- $N$ $Q$\n- $D$ $A$ $B$\n- $L_1$ $R_1$\n- $L_2$ $R_2$\n- ...\n- $L_N$ $R_N$\n- $X_1$\n- $X_2$\n- ...\n- $X_Q$\n\n## Output\n\n输出 $Q$ 行，在第 $j$ 行（$1 \\leq j \\leq Q$）输出 JOI 君到达第 $X_j$ 级台阶所需的最少秒数；如果无法到达，则输出 $-1$。\n\n[samples]\n\n## Note\n\n#### 样例解释 1\n\nJOI 君可以按照以下步骤在 $120$ 秒内到达楼梯的第 $13$ 阶：\n\n- 从第 $0$ 阶到第 $1$ 阶上升。此操作需要 $10$ 秒。\n- 从第 $1$ 阶到第 $2$ 阶上升。此操作需要 $10$ 秒。\n- 从第 $2$ 阶到第 $3$ 阶上升。此操作需要 $10$ 秒。\n- 从第 $3$ 阶跳到第 $7$ 阶，跳过中间的台阶。此操作需要 $35$ 秒。\n- 从第 $7$ 阶到第 $8$ 阶上升。此操作需要 $10$ 秒。\n- 从第 $8$ 阶到第 $9$ 阶上升。此操作需要 $10$ 秒。\n- 从第 $9$ 阶跳到第 $13$ 阶，跳过中间的台阶。此操作需要 $35$ 秒。\n\n由于无法在小于 $120$ 秒内到达第 $13$ 阶楼梯，输出为 $120$。\n\n这个样例输入满足子任务 $1,2,4$ 的约束条件。\n\n#### 样例解释 2\n\n这个样例输入满足子任务 $1,2,4$ 的约束条件。\n\n### 约束条件\n\n- $1 \\leq N \\leq 200,000$\n- $1 \\leq Q \\leq 200,000$\n- $1 \\leq D \\leq 10^{12}$\n- $1 \\leq A \\leq 1,000,000$\n- $1 \\leq B \\leq 1,000,000$\n- $1 \\leq L_i \\leq R_i \\leq 10^{12}$（$1 \\leq i \\leq N$）\n- $R_{i}+1 < L_{i+1}$（$1 \\leq i \\leq N-1$）\n- $1 \\leq X_j \\leq 10^{12}$（$1 \\leq j \\leq Q$）\n- 给定值均为整数。\n\n### 子任务\n\n1. （5 分）$R_i \\leq 1,000,000$（$1 \\leq i \\leq N$），$X_j \\leq 1,000,000$（$1 \\leq j \\leq Q$）\n2. （38 分）$N \\leq 2,000$，$Q \\leq 2,000$\n3. （25 分）$A = 1$，$B = D$\n4. （32 分）无额外约束。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10438","tags":["2024","JOISC/JOIST（日本）"],"sample_group":[["3 1\n4 10 35\n4 5\n10 12\n14 14\n13","120"],["5 10\n10 1 9\n7 11\n25 32\n37 38\n43 44\n50 52\n6\n12\n18\n24\n30\n36\n42\n48\n54\n60","6\n11\n17\n22\n-1\n33\n-1\n44\n-1\n55"]],"created_at":"2026-03-03 11:09:25"}}