책 배치

면접 대비

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

요약

책 n권을 일렬로 배열할 때, 인접한 두 책의 쪽수 합이 그 사이의 제한값 a_i를 넘지 않는 배열의 개수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 완전 탐색, 백트래킹
정답자: 아직 제출이 없습니다

문제

학년 초, 한 대학 도서관이 학생들에게 책을 빌려주어 학생들이 한 해 동안 공부에 쓸 수 있게 했다. 학생 올레치카는 긴 줄을 기다려 책을 받은 뒤, 힘겹게 책을 집까지 들고 왔다. 이제 올레치카는 이 학술서들을 자기 책장에 꽂으려 한다.

아쉽게도 올레치카는 책이 어떻게 꽂혀 있는지에 따라 기분이 좋지 않다. 책장에서 나란히 꽂힌 두 책의 쪽수 합이 일정 값을 넘으면 그녀는 속상해한다.

더 정확히 말하면, 책장의 $i$ 번째와 $(i+1)$ 번째 자리에 놓인 두 책의 전체 쪽수가 $a_i$ 보다 크면 올레치카는 속상해한다.

가엾은 올레치카가 속상하지 않도록 책을 책장에 꽂는 방법이 몇 가지인지 알려 주세요.

입력

첫 줄에 올레치카의 책 개수 $n$ ( $1 \le n \le 9$ )이 주어진다. 둘째 줄에는 각 책의 쪽수 $p_i$ ( $1 \le p_i \le 10^9$ )가 $n$ 개 주어진다. 셋째 줄에는 책장의 $i$ 번째와 $i+1$ 번째 자리에 놓인 두 책의 전체 쪽수 허용 한도 $a_i$ ( $1 \le a_i \le 2 \cdot 10^9$ )가 $n-1$ 개 주어진다.

출력

책을 책장에 꽂는 방법의 수를 출력한다.

예제2

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