코딩 테스트

회사는 요즘 늘어난 코딩 테스트의 인기에 힘입어 코딩 테스트용 문제를 만들어 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$ 단계로 평가된 문제는 난이도를 둘 증 하나로 적절히 설정해서 판매하는 세트 개수가 최대한 많아지도록 해야 하며, 판매하는 모든 세트에 걸쳐 같은 문제가 여러 번 들어기지 않도록 해야 한다.

코딩 테스트

문제

제한