코딩 테스트

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

요약

난이도가 애매한 문제를 두 단계 중 하나로 배정할 수 있을 때, 각 기업 구간마다 난이도별로 문제 하나씩 담은 세트의 최대 개수를 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 이분 탐색, 누적 합
정답자: 아직 제출이 없습니다

문제

요즘 코딩 테스트의 인기가 높아지면서, 회사는 코딩 테스트용 문제를 만들어 IT 기업에 판매하고 있다.

회사는 편의를 위해 문제의 난이도를 $0$ 단계부터 $N-1$ 단계까지 나누었다. 현재 회사에는 난이도가 $i$ 단계로 평가된 문제가 $A[i]$ 개 준비되어 있다. 또한 난이도 평가가 애매해서 $i$ 단계 혹은 $i+1$ 단계로 평가된 문제도 $B[i]$ 개 준비되어 있다. 이외의 방식으로 난이도가 평가된 문제는 없다.

회사는 지금 문제를 판매할 기업을 찾고 있다. 현재 구매 의향을 나타낸 기업은 총 $M$ 곳이며, $0$ 부터 $M-1$ 까지 번호가 붙어 있다. $j$ ( $0 \le j \le M-1$ )번 기업은 회사의 문제 중 난이도가 $L[j]$ 단계 이상이고 $U[j]$ 단계 이하인 문제에만 관심이 있다.

회사는 $j$ 번 기업에게 문제를 판매할 때, $L[j]$ 단계부터 $U[j]$ 단계까지의 문제를 난이도별로 하나씩 뽑아 묶음으로 판매하려고 한다. 이 묶음을 세트라고 하자.

$j$ 번 기업에게만 문제를 판매한다면, 최대 몇 개의 세트를 판매할 수 있을까?

난이도가 $i$ 단계 혹은 $i+1$ 단계로 평가된 문제는 두 난이도 중 하나로 적절히 설정해서, 판매하는 세트 개수가 최대한 많아지도록 해야 한다. 또한 판매하는 모든 세트에 걸쳐 같은 문제가 두 번 이상 들어가지 않도록 해야 한다.

제한

$2 \le N \le 100000$
$1 \le M \le 100000$
모든 $0 \le i \le N-1$ 에 대해 $0 \le A[i] \le 10^8$
모든 $0 \le i \le N-2$ 에 대해 $0 \le B[i] \le 10^8$
모든 $0 \le j \le M-1$ 에 대해 $0 \le L[j] \le U[j] \le N-1$

예제1

예제 1
입력
```
2 1
0 0
0
1 1
```
예상 출력
```
0
```