First of all , Dr. Bea evaluates he working time for every team . Judging by their loads , he thinks that p[i] seconds is needed by the i-th team . Dr. Bea also gives each team a time r[i] so that the i-th team must get ready to work . For example :
P[i] 4 2 6 5
r[i] 0 1 3 5
In this example , team zero can start their work at the very beginning ( time 0 means the beginning time of the day ) and must finish in 4 seconds , and team one can’t work before the first second but can in any time after it , etc .
Different team has different task , including laying the desks , installing the system and so on . To avoid conflicts , Dr. Bea will only allow one team in the lab at any time .
At last , Dr. Bea sets up a due time d[i] for each team . Because the due time is coming from Bea’s evaluation , it may be impossible to have a schedule satisfy all this constraints . So the lateness is the difference between the finishing time and the due time . Suppose a team starts the work in the s second , so they will finish their work in s+p . If their due time is d ,then the lateness is (s+p)-d.
Continue with the example ,all four teams due time is given below :
d[i] 8 12 11 10
We have many strategies to make the schedule . By the order of they comes , we can set team zero work from time 0 to time 4 , team one from 4 to 6 , team two from 6 to 12 , and team three from 12 to 17 . Their lateness is -4 , -6 , 1 and 7 respectively . The maximum lateness among all four teams is 7 , which is of team three . But if we put team two to the last , their maximum lateness will be 5 .
The input consists of multiple data sets . The end of the input is indicated by a line containing a zero .
The format of each dataset is as follows .
p1p2 … pn
r1r2 … rn
d1d2 … dn
Here , all data items are positive integers . n is the number of teams ( n<=100 ) . n integers p1 … pn , in the second line , are the working time for each team , integers r1 … rn are ready time , integers d1 … dn are due time . All these integers are no more than 1000 .
For each data set , output the maximum lateness in the schedule you found , in a separate line .
4 2 6 5
0 1 3 5
8 12 11 10