← 返回题目列表

Codeforces · 57/B

B. 火星建筑

中文机器翻译题面 查看原题

兔子克里斯发现了古代火星文明的痕迹。这位勇敢的天文学家设法通过小型望远镜看到了建筑杰作——“通往太阳的道路”。这座建筑矗立在同样大小的立方体石头上。地基将整条“路”划分为多个单元,立方体的石头紧密地嵌入其中。因此,可以将坐标分配给基础的任何单元。要成为部落的领导者,火星人应该建造一条通往太阳的道路,即在给定的基础上用这些立方体石头建造楼梯。楼梯应该通过初始坐标中的石头数量以及楼梯起点和终点的坐标来描述。坐标递增顺序中的每个后续单元格应比前一个单元格多包含一个立方体石头。如果牢房里已经有了石头,那么它们就不算在这个建造过程中,楼梯只是建在它们上面。换句话说,我们假设用初始坐标l、最终坐标r和初始坐标x中的石头数量建造了一个楼梯。这意味着 x 个石头将被添加到单元格 l 中,x + 1 个石头将被添加到单元格 l + 1 中,...,x + r - l 个石头将被添加到单元格 r 中。

克里斯设法找到了一份古老的手稿,其中包含所有楼梯的描述。现在他要对比一下数据,确定自己真的找到了《太阳之路》。为此,他选择了一些道路单元,计算了整个火星历史中积累的立方体石头的总数,然后要求你使用手稿来计算理想的总和。

输入

第一行包含三个空格分隔的整数:n、m、k (1 ≤ n, m ≤ 105, 1 ≤ k ≤ min(n, 100)),分别是单元格数量、“Roads to the Sun”的数量和查询中单元格的数量。以下 m 条道路中的每条都包含三个以空格分隔的整数:ai, bi, ci (1 ≤ ai ≤ bi ≤ n, 1 ≤ ci ≤ 1000),它们是楼梯的描述、其起点、终点和初始单元的高度。然后是一行,包含 k 个不同的空格分隔整数 bi。所有这些从 1 到 n 的数字都是单元格,即克里斯感兴趣的石头数量。

输出

你必须在一行上打印一个数字,这是克里斯感兴趣的所有单元格中石头的总和。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin (也可以使用 %I64d)。

示例

输入 #1

5 2 1
1 5 1
2 4 1
3

输出 #1

5

输入 #2

3 2 1
1 3 1
1 3 1
2

输出 #2

4

输入 #3

3 2 1
1 3 1
1 3 1
3

输出 #3

6