29583번 - Расстановка книг 다국어

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

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

Говоря более точно, Олечка сильно расстраивается, если существует пара книг, стоящих на местах $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$ полки.

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