문제 보기 - 운세 보기 2 (JOI14_fortune_telling2)

시간 제한 메모리 제한 제출 횟수 통과한 사람 수 비율
3000 ms 256 MiB 1274 287 22.53%

K 교수는 일본 IOI 위원회의 위원장입니다. 그는 운세 보기를 좋아합니다. 그는 항상 여러 종류의 운세를 보고 있습니다. 오늘, 그는 일본 IOI 국가대표들의 결과를 예측하기 위해 카드를 이용하여 운세를 보기로 했습니다.

카드의 양 면에는 정수가 쓰여 있으며 일치한다는 보장은 없습니다. 만약 여러분이 이 카드를 책상 위에 놓으면, 한 면의 정수는 볼 수 있으나, 다른 쪽의 정수는 가려져 보이지 않습니다.

운세 보기는 아래와 같은 과정으로 진행됩니다.

  • 처음, K 교수는 책상 위에 $N$개의 카드를 놓습니다. 각 카드는 $1$ 이상 $N$ 이하의 번호가 붙어 있습니다. $i$번 카드의 한 쪽 면에는 정수 $A_{i}$가, 다른 쪽 면에는 정수 $B_{i}$가 쓰여 있습니다. 그는 각 카드 $i$에 대해 $A_{i}$가 보이도록 카드를 놓습니다.
  • 각 $j = 1, \cdots, K$에 대해 그는 다음 연산을 차례대로 수행합니다: "만약 어떤 카드에서 보이는 면의 정수가 $T_{j}$ 이하이면, 해당 카드를 뒤집는다."
  • 운세의 결과는 이 $K$개의 연산이 끝난 후 탁자 위에 놓인 카드들의 보이는 면에 쓰여 있는 정수들의 합이 됩니다.

K 교수는 각 연산을 수행할 때마다 어떤 카드가 뒤집힐지 결정하는 것이 매우 지루해졌습니다. 그는 마침내 카드를 이용한 운세 보기를 포기하였습니다. 그는 단지 $K$개의 연산이 모두 수행되었을 때 카드의 보이는 면에 쓰인 정수들의 합을 구하고자 합니다.

해야 할 일

카드에 쓰인 정수들과 연산의 정보가 주어질 때, 모든 연산이 끝난 뒤 카드의 보이는 면에 적힌 정수들의 합을 구하는 프로그램을 작성하세요.

입력

표준 입력에서 아래 데이터를 받으세요.

  • 첫 번째 줄에 두 개의 정수 $N$과 $K$가 공백을 사이로 두고 주어집니다. 이것은 $N$개의 카드가 있으며 연산의 수는 $K$임을 의미합니다.
  • 다음 $N$개 줄에서 $i$번째 줄 ($ 1 \le i \le N$)에는 두 개의 정수 $A_{i}$와 $B_{i}$가 공백을 사이로 두고 주어집니다. 이것은 $i$번 카드의 양면에 쓰여 있는 정수가 $A_{i}$와 $B_{i}$라는 것입니다.
  • 다음 $K$개 줄에서 $j$번째 줄 ($1 \le j \le K$)에는 정수 $T_{j}$가 주어집니다. 이것은, $j$번째 연산에서, 카드의 보이는 면에 쓰인 숫자가 $T_{j}$ 이하라면 이 카드는 뒤집어진다는 것을 의미합니다.

출력

표준 출력에, $K$번의 연산을 모두 수행한 후 책상 위에 놓인 카드들의 보이는 면에 쓰인 정수들의 합을 출력합니다.

제약 조건

모든 입력 데이터는 아래 조건을 만족합니다.

  • $1 \le N \le 200,000$
  • $1 \le K \le 200,000$
  • $1 \le A_{i} \le 1,000,000,000$ ($1 \le i \le N$)
  • $1 \le B_{i} \le 1,000,000,000$ ($1 \le i \le N$)
  • $1 \le T_{j} \le 1,000,000,000$ ($1 \le j \le K$)

서브태스크

서브태스크 1 [4점]

  • $N \le 1,000$
  • $K \le 1,000$

서브태스크 2 [31점]

  • $N \le 40,000$
  • $K \le 40,000$

서브태스크 3 [65점]

추가 제약 조건이 없습니다.

입출력 예제

입력 출력
5 3
4 6
9 1
8 8
4 2
3 7
8
2
9
18

4, 9, 8, 4, 3 -> 6, 9, 8, 2, 7 -> 6, 9, 8, 4, 7 -> 4, 1, 8, 2, 3