JOI Open 2014- Fortune Telling 2 > 문제은행 : 정보올림피아드&알고리즘




3595 : Fortune Telling 2

제한시간
2000 ms   
메모리제한
1024 MB   
해결횟수
3 회   
시도횟수
16 회   

문제

일본의 Prof. K는 일본 IOI 커뮤니티의 위원장이다. 그는 운세를 좋아해서, 언제나 여러 종류의 운세를 확인한다. 오늘, 그는 카드를 사용하는 운세를 이용해서 일본 대표단의 결과를 확인해보기로 했다.

 

카드의 양면 각각에는 수가 하나씩 쓰여있다. 두 수는 같을 필요는 없다. 만약 카드가 테이블에 놓여있다면, 카드의 윗면에 쓰인 숫자만 볼 수 있고, 밑면에 쓰인 숫자는 볼 수 없다.

 

운세는 아래와 같이 진행된다.

 

 

  1. 1. 먼저, Prof. K는 N개의 카드를 테이블에 놓는다. 카드는 1부터 N까지의 번호가 붙어있다. i번째 카드에는 Ai와 Bi가 쓰여있다. Prof. K는 항상 Ai가 위로 오도록 카드를 놓는다.
  2. 2. 모든 j=1, …, K에 대해, Prof. K는 다음과 같은 작업을 반복한다. “카드의 윗면에 쓰인 숫자가 Tj보다 작거나 같다면, 카드를 뒤집는다.”
  3. 3. 운세의 결과는 K번의 작업이 끝난 후 모든 카드의 윗면에 쓰인 숫자의 총합이다.

 

 

Prof. K는 위의 작업을 손수 직접 하다가 너무 귀찮아졌다. 마침내 그는 카드를 뒤집는 작업을 포기하고, 결과만을 원하기 시작했다.

 

Prof. K를 도와 모든 작업을 끝냈을 때, N개의 카드에 보이는 숫자의 총합을 출력하는 프로그램을 작성하여라.​ 


입력형식

첫째 줄에 카드의 개수 n과 작업의 수 k가 주어진다. (1 ≤ n, k ≤ 200,000)

 

다음 n개의 줄에는 카드에 적힌 수 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 109)

 

다음 K개의 줄에는 각 작업에서 확인하는 카드의 수를 의미하는 수 Tj가 주어진다. (1 ≤ Tj ≤ 109)

 


출력형식

모든 작업이 끝났을 때, 모든 카드의 윗면에 쓰인 숫자의 총합을 출력한다.

 


입력 예

5 3
4 6
9 1
8 8
4 2
3 7
8
2
9

출력 예

18

Hint!

제일 처음에 카드는 4, 9, 8, 4, 3이 보이게 놓여있다. 각 작업이 끝난 후 테이블의 상태는 다음과 같다.

 

8보다 작거나 같은 수를 뒤집는다. 6, 9, 8, 2, 7

2보다 작거나 같은 수를 뒤집는다. 6, 9, 8, 4, 7

9보다 작거나 같은 수를 뒤집는다. 4, 1, 8, 2, 3

 

총합은 4+1+8+2+3 = 18이다.​ 




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP