Cave Allocation Peace

On the island of Crete, there are m caves arranged in a circle and numbered clockwise from \(1\) to \(m\). There are \(n\) cavemen living on the island. Initially, the \(i\)th caveman occupies cave \(C_i\). After that, every year the \(i\)th caveman moves forward by \(P_i\) caves in the clockwise direction and occupies the new cave. Each caveman has a lifespan of \(L_i\) years, meaning he is alive from year \(0\) up to year \(L_i-1\) (with year 0 being the initial state).

For a chosen \(m\), the position of the \(i\)th caveman in year \(t\) (with \(0 \le t < L_i\)) is given by the formula:

[ \text{pos}_i(t) = \Bigl( (C_i-1) + t \cdot P_i \Bigr) \mod m + 1. ]

It is observed that, remarkably, no two cavemen ever occupy the same cave in any year during which both are alive. The scientists on the island wonder: what is the minimum number \(m\) of caves required to maintain this everlasting peace?

inputFormat

The first line contains a single integer \(n\) (the number of cavemen).
The second line contains \(n\) integers \(C_1, C_2, \dots, C_n\) representing the initial cave numbers of the cavemen.
The third line contains \(n\) integers \(P_1, P_2, \dots, P_n\) representing the number of caves each caveman moves forward every year.
The fourth line contains \(n\) integers \(L_1, L_2, \dots, L_n\) representing the lifespan (in years) of each caveman.

All numbers are separated by spaces.

outputFormat

Output a single integer, which is the minimum number \(m\) of caves such that during the lifetime of every caveman, no two cavemen are ever in the same cave at the same time.

sample

3
1 2 3
3 7 2
4 3 1

6