配点 : 600 点
問題文
縦 H 行、横 W 有一个列网格。下面,左上角的正方形 (1, 1) 以及上面 x 行,从左起 y 选择列中的方块。 (x, y) 。
这个广场上有一个矩形结构。 N 它是独立的。 i 第二个结构是 U_i \leq x \leq D_i, L_i \leq y \leq R_i 它覆盖了所有 (x, y) 而没有其他方块。在这里, 1 只有一个结构可以覆盖一个正方形。 1 保证是。此外,每个结构都有一个值 我有 C_i 。
将每个方块的值定义为覆盖该方块的结构的值。然而,如果没有结构覆盖该正方形,则该正方形的值为 假设它是 0 。
猎鹰先生有一把波动枪,可以摧毁射击位置右侧的所有方块。严格来说,大众 当你用 (x, y) 发射波动炮时, 所有满足 y \leq j \leq W 的整数 关于 j 关于质量 (x, j) 可以被摧毁。
此时,Falcon的幸福感将是被摧毁的方块的总价值。
该波动枪可以自由上下移动,但不能左右移动。安装波动炮的候选行 Q 单独定义,每个 K_i 列。求每种情况下法尔肯幸福感的最大值。
制約
- 1 \leq N \leq 10^5
- 1 \leq H,W \leq 10^9
- 1 \leq U_i \leq D_i \leq H (1 \leq i \leq N)
- 1 \leq L_i \leq R_i \leq W (1 \leq i \leq N)
- 2 同一方块上不超过一个结构。
- 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq K_i \leq W (1 \leq i \leq Q)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N H W U_1 D_1 L_1 R_1 C_1 U_2 D_2 L_2 R_2 C_2 \vdots U_N D_N L_N R_N C_N Q K_1 K_2 \vdots K_Q
出力
输出答案。
入力例 1
4 6 14 1 5 1 2 3 4 6 3 4 4 2 4 5 7 8 1 1 4 13 3 4 1 5 11 13
出力例 1
38 27 9 3
网格将如下所示:

例如 自从 1 从行射击时,
- 1 如果你把它放在行上,幸福将会是 36
- 2 如果你把它放在行上,幸福将会是 30
- 3 如果你把它放在行上,幸福将会是 30
- 4 如果你把它放在行上,幸福将会是 38
- 5 如果你把它放在行上,幸福将会是 14
- 6 如果你把它放在行上,幸福将会是 8
,所以 请输出 38 。 我有一个带有
入力例 2
10 100 100 69 94 13 36 36 37 83 82 86 31 20 32 60 60 14 56 63 57 58 93 87 92 68 70 72 88 90 76 95 75 55 66 2 3 74 2 7 77 92 30 82 83 67 74 37 21 76 52 53 4 10 93 29 57 6 82 88 95 79 59 3
出力例 2
225 2004 1716 2580 1050 600 75 1275 1716 2580