카드 공장 (Large)
시간 제한3초메모리 제한256 MB
N개의 카드가 처음에는 앞면을 보이며, K 이하의 수가 보이는 카드를 모두 뒤집는 질의가 M번 주어질 때 마지막으로 보이는 수의 합을 구한다.
문제
진서는 CTP 카드 공장의 노동자이다. 공장에는 N개의 카드가 있고, 각 카드에는 앞면과 뒷면에 숫자가 쓰여 있다. 공장장 노진의 명령에 따라 진서는 카드를 뒤집어야 한다. 명령은 M번 내려지며, 명령은 다음과 같다.
"공장장 노진이 K라는 수를 말하면 진서는 N개의 카드 중 보이는 면이 K 이하인 카드를 모두 뒤집어야 한다."
공장장의 명령이 끝났을 때, 진서는 카드의 보이는 면의 수들의 합을 공장장에게 보고해야 한다.
예를 들면 다음 그림과 같다.
카드는 처음에 모두 앞면이 보이도록 세팅되어 있고, 카드에 적힌 수는 10억 이하의 자연수이다.
입력
첫 번째 줄에 N과 M이 주어진다. (N, M은 200,000 이하의 자연수)
그다음 N개의 줄에 카드의 앞면 Ai와 뒷면 Bi가 주어진다. (Ai와 Bi는 10억 이하의 자연수)
그다음 M개의 줄에 공장장이 말하는 수 K가 주어진다. (K는 10억 이하의 자연수)
출력
명령이 끝났을 때 보이고 있는 카드들의 합을 출력한다.