Arranging Books

Interview

Time limit2sMemory limit1024 MB

Summary

Count the orderings of n books on a shelf where every adjacent pair's combined page count is at most the limit a_i between them.

Level: Easy3 of 10
Topics: Brute force, Backtracking
Solved: No attempts yet

Problem

At the start of the school year, the library of a large university lent books to its students so they could study over the year. Olechka, a student, waited in a huge line, received her books, and carried them home with great effort. Now she wants to place these scientific works on her bookshelf.

Unfortunately, Olechka is not happy with every arrangement. She is upset by any two neighboring books on the shelf whose combined page count is more than a given value.

More precisely, Olechka becomes upset if there is a pair of books in positions $i$ and $(i+1)$ of the shelf whose total number of pages is greater than $a_i$ .

Help poor Olechka find how many ways there are to arrange the books on the shelf so that she is not upset.

Input

The first line contains the number $n$ ( $1 \le n \le 9$ ), the number of Olechka's books. The second line contains $n$ integers $p_i$ ( $1 \le p_i \le 10^9$ ), the number of pages in each book. The third line contains $n-1$ integers $a_i$ ( $1 \le a_i \le 2 \cdot 10^9$ ), the allowed total number of pages in the books at positions $i$ and $i+1$ of the shelf.

Output

Print the number of ways to arrange the books on the shelf.

Examples2

Example 1
Input
```
3
1 2 1
2 3
```
Expected output
```
2
```
Example 2
Input
```
3
1 1 2
1 2
```
Expected output
```
0
```