Preparing NOJ

# Preparation

5000ms 65536K

## Description:

ZSUCPC is an annual event for collegiate students . Here they challenge their programming skills , develop their friendship . This year’s event will be coming soon . The staffs and judges are busy to make preparations . Many working teams are going to arrange the lab . In order to make people work efficiently , Dr. Bea , the director , has to make a plan for a day .

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 :

I                 0                1                2                3

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 :

I                 0                1                2                3

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 .

Now Dr. Bea puts his focus on the maximum lateness among all the teams . He wants to find out a schedule that reduces the maximum lateness as possible .

## Input:

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 .

n

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 .

## Output:

For each data set , output the maximum lateness in the schedule you found , in a separate line .

## Sample Input:

44 2 6 50 1 3 58 12 11 100

## Sample Output:

5

## Note:

Info

Provider NOJ

Code NOJ1140

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet