E - 壊れかけのコンピュータ 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

問題文

あなたは壊れかけのコンピュータを入手しました。 このコンピュータは足し算をすることができますが、ある特定の N 組の数のペアについては、その和をいつも誤って計算してしまいます。 具体的には、各 i\ (1\leq i\leq N) に対して、A_i+B_i および B_i+A_i の値を 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
  • 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 の和を計算する過程では 1+1 という式は出てこないので、正しい答えを求めることができます。

入力例 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

Problem Statement

You acquired a malfunctioning computer. This computer is capable of computing addition, but always reports a wrong sum for specific N pairs. Specifically, for all i\ (1\leq i\leq N), it evaluates A_i+B_i and B_i+A_i to C_i. Conversely, it finds correct sums for any other pairs of numbers.

You found a program that computes the sum of several numbers. When M numbers x_1,x_2,\dots and x_M are input to this program, this computer finds their sum by the following procedure.

  1. Initialize a variable s with x_1.
  2. For each i=2,3,\dots,M in order:
    • evaluate s+x_i, and assign the result to s.
  3. Print the final value of s.

Find what will be printed when M numbers X_1,X_2,\dots, and X_M are input to this program.

Constraints

  • 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, then (A_i,B_i)\neq (A_j,B_j).
  • A_i+B_i \neq C_i
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

5

This computer finds the sum of 1,3,4, and 2 as follows.

  1. Initialize a variable s with 1.
  2. Evaluate 1+3\ (=A_2+B_2) wrongly to 2\ (=C_2), and assign it to s.
  3. Evaluate 2+4 correctly to 6, and assign it to s.
  4. Evaluate 6+2\ (=B_3+A_3) wrongly to 5\ (=C_3), and assign it to s.
  5. Print the final value of s, that is, 5.

Sample Input 2

1 3
1 1 1
1 2 3

Sample Output 2

6

While this computer always wrongly evaluates 1+1, this is never evaluated when finding the sum of 1,2, and 3, so it prints the correct sum.

Sample Input 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

Sample Output 3

3