울타리 짓기

시간 제한1초메모리 제한1024 MB

요약

쓰러진 나무 구간 N개와 인부 위치 M개가 주어질 때, 각 나무를 내부에 있는 인부마다 잘라 생기는 조각 길이의 합을 구한다.

난이도: 보통10점 중 7점
유형: 정렬, 이분 탐색, 구간, 누적 합
정답자: 아직 제출이 없습니다

문제

야생 동물들의 습격을 자주 당하는 마을 사람들이 마을을 뾰족 나무 울타리로 감싸려고 한다. 사람들은 나무를 도끼로 내려찍어 나무들이 겹치지 않도록 하며 좌우로 쓰러트렸다. 인부들은 한자리에서 서서 내려가면서 나무가 쓰러진 첫 지점을 시작점으로 양쪽이 뾰족하도록 깎은 후, 깎은 나무들로 마을을 둘러싸는 울타리를 지으려 한다. 단, 인부의 위치와 나무가 쓰러진 끝 지점이 같으면 나무를 깎을 수 없다.

작업을 마친 후, 마을 사람들을 대신해 울타리 조각들의 총길이를 구해주자.

예를 들어, 그림의 첫 번째 나무에서는 (1, 2), (4, 8) 두 개의 울타리 조각을 얻고, 두 번째 나무에서는 (8, 10), (12, 15) 두 개의 울타리 조각을 얻어 총길이는 1 + 4 + 2 + 3 = 10이 된다.

입력

첫 번째 줄에 사람들이 쓰러트린 나무의 수 $N$ 과 인부의 수 $M$ 이 공백으로 구분되어 주어진다. $(1 \leq N, M \leq 10^{5})$

두 번째 줄부터 $N$ 개의 줄에 걸쳐 나무가 쓰러진 첫 지점 $S\_i$ 와 끝 지점 $E\_i$ 가 공백으로 구분되어 주어진다. $(1 \leq S\_i, E\_i \leq 10^{9};$ $S\_i \neq E\_i)$

나무가 오른쪽으로 쓰러졌다면 $S\_i < E\_i$ 이고, 나무가 왼쪽으로 쓰러졌다면 $S\_i > E\_i$ 이다.

$N + 2$ 번째 줄부터 $M$ 개의 줄에 걸쳐 인부들이 서 있는 위치 $L\_i$ 가 주어진다. 인부들이 서 있는 위치는 중복해서 주어지지 않는다. $(1 \leq L\_i \leq 10^{9})$

모든 입력은 정수이다.

출력

울타리 조각들의 총길이를 출력한다.

예제3

예제 1
입력
```
2 5
1 11
15 5
2
4
8
10
12
```
예상 출력
```
10
```
예제 2
입력
```
1 5
1 11
2
3
5
7
11
```
예상 출력
```
3
```
예제 3
입력
```
3 4
3 20
37 11
12 45
5
19
12
35
```
예상 출력
```
25
```