URI Online Judge | 1505

Curo Factories

By Andre Quispesaravia, PUCP PE Peru

Timelimit: 6

Here in Curoland are N factories that are identified by the numbers from 0 to n-1. The ith factory pays Ci coins each day to the people working there.  Initially, there are one worker in every factory. The workers want to save some coins for their vacations, the worker that initially was in the ith factory wants to save Ai coins.

Little Curo, the mayor of Curoland, wants some job rotation in factories so they don't become bored of their jobs. That's why every day, after the factories pays they workers for their job, the workers in the ith Factory have to move to the Gi Factory.

Little Curo wants to know the minimum number of days he have to wait until every worker have saved enough for their vacations. Because that day he will give a big party for them.

Input

The input is composed of 4 lines. In line 1 there is a number N. The lines 2 to 4 have N numbers. The i-th number of the line 2 is Gi (0 < Gi < N), the i-th number of the line 3 is Ci (0 < Ci <= 10) and the i-th number of the line 4 is Ai (0 < Ai < 107)

Output

The program has to print the minimum number of days little Curo has to wait until every worker have saved enough.

Sample Input Sample Output

3
2 0 1
2 5 7
15 15 15

4