← 返回题目列表

AtCoder · past21_e

E. 电脑坏了

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

问题陈述

您购买了一台有故障的计算机。 这台计算机能够计算加法,但总是报告特定的错误总和 N 对。 具体来说,对于所有 i\ (1\leq i\leq N),它评估 A_i+B_i 和 B_i+A_i to C_i。 相反,它会找到任何其他数字对的正确总和。

您找到了一个计算多个数字之和的程序。 当 M 号码 x_1,x_2,\dots 和 x_M 被输入到该程序中,该计算机通过以下过程求出它们的和。

  1. 初始化变量 s 与 x_1.
  2. 对于每个 i=2,3,\dots,M 按顺序:
    • 评估 s+x_i,并将结果分配给 s.
  3. 打印最终值 s.

查找以下情况下将打印的内容 M 号码 X_1,X_2,\dots,和 X_M 被输入到该程序中。

约束

  • 1\leq N \leq 2\times 10^5
  • 2\leq M \leq 2\times 10^5
  • 0\leq A_i,B_i,C_i,X_i \leq 10^9
  • A_i \leq B_i
  • If i\neq j,那么 (A_i,B_i)\neq (A_j,B_j).
  • A_i+B_i \neq C_i
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N
X_1 X_2 \dots X_M

输出

打印答案。


样本输入 1

3 4
4 9 0
1 3 2
2 6 5
1 3 4 2

示例输出 1

5

这台计算机找到的总和 1,3,4,和 2 如下。

  1. 初始化变量 s 与 1.
  2. 评估 1+3\ (=A_2+B_2) 错误地 2\ (=C_2),并将其分配给 s.
  3. 评估 2+4 正确地 6,并将其分配给 s.
  4. 评估 6+2\ (=B_3+A_3) 错误地 5\ (=C_3),并将其分配给 s.
  5. 打印最终值 s,即 5.

示例输入 2

1 3
1 1 1
1 2 3

示例输出 2

6

虽然这台计算机总是错误地评估 1+1,在求总和时不会评估这一点 1,2,和 3,因此它打印正确的总和。


示例输入 3

8 10
5 27 27
8 72 27
2 27 12
3 32 12
57 60 3
35 57 27
12 41 72
12 64 57
57 60 32 64 0 60 32 64 0 60

示例输出 3

3