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:

4
4 2 6 5
0 1 3 5
8 12 11 10
0

Sample Output:

5

Note:

本题由旧版NOJ导入,来源:NUPT ACM

Info

NOJ

Provider NOJ

Code NOJ1140

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet