Расстановка книг

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

요약

책 n권(n <= 9)의 순열 중에서 인접한 두 책의 페이지 합이 각 위치의 한도 a_i 이하인 배열의 수를 센다.

난이도: 보통10점 중 4점
유형: 완전 탐색, 백트래킹, 조합론
정답자: 아직 제출이 없습니다

문제

В начале учебного года в одном Великом Университете библиотека выдавала книги своим студентам, чтобы они использовали их для получения познаний в течении года. Студентка Олечка, отстояв огромную очередь и получив книги в библиотеке, с великим трудом донесла их до своего дома. Теперь Олечка хочет расставить эти научные труды на свою книжную полку.

К сожалению, с восприятием содержимого книжной полки своей хозяйкой не так все просто --- Олечку приводят в уныние книги, стоящие на полке по соседству и имеющие в общей сложности количество страниц, превышающее некоторое значение.

Говоря более точно, Олечка сильно расстраивается, если существует пара книг, стоящих на местах $i$ и $(i+1)$ полки, и общее число станиц в этих двух книгах превышает $a\_i$ .

Помогите бедной Олечке понять, сколько способов существует расставить книги на полке так, чтобы она не расстраивалась.

입력

В первой строке входного файла записано число $n$ ( $1 \le n \le 9$ ) --- число Олечкиных книг. В второй строке находится $n$ чисел $p\_i$ ( $1 \le p\_i \le 10^9$ ) --- количество страниц в каждой из книг. В третьей строке находится $n-1$ число $a\_i$ ( $1 \le a\_i \le 2 \cdot 10^9$ ) --- допустимое общее количество страниц в книгах, стоящих на местах $i$ и $i+1$ полки.

출력

В выходной файл выведите количество способов расставить книги на полке.

예제2

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