| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 27 | 22 | 16 | 80.000% |
В начале учебного года в одном Великом Университете библиотека выдавала книги своим студентам, чтобы они использовали их для получения познаний в течении года. Студентка Олечка, отстояв огромную очередь и получив книги в библиотеке, с великим трудом донесла их до своего дома. Теперь Олечка хочет расставить эти научные труды на свою книжную полку.
К сожалению, с восприятием содержимого книжной полки своей хозяйкой не так все просто --- Олечку приводят в уныние книги, стоящие на полке по соседству и имеющие в общей сложности количество страниц, превышающее некоторое значение.
Говоря более точно, Олечка сильно расстраивается, если существует пара книг, стоящих на местах $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$ полки.
В выходной файл выведите количество способов расставить книги на полке.
3 1 2 1 2 3
2
3 1 1 2 1 2
0