Indian National Olympiad in Informatics

Related:

Online Programming Contest, 15-16 July, 2006

IARCS home > OLYMPIAD

Advanced Division

Problem 2: State of the kingdom address, (K Narayan Kumar, CMI)

After unauthorisedly extending his vacation by a week, Ramu returns to his office to find a huge backlog of pending jobs, all of which are well past their deadlines. His boss is furious with him and decides to levy a penalty for each pending job.

Each pending job j takes a certain number of days to finish. Once Ramu starts a job, he must finish it before he can take up any other job. The penalty levied by Ramu's boss varies from one job to another. For each job, the penalty depends on the day on which Ramu finishes it: if job j is completed d days from today, the penalty is a_j d² + b_j d + c_j. Moreover, for each job, the penalty is guaranteed to increase as the number of days taken to complete the job grows.

The task is to find a schedule for Ramu to finish all his pending jobs so that the maximum penalty he pays for any job is minimized.

For instance, suppose there are three pending jobs. Job 1 takes 3 days to complete and the penalty associated with this job is 3d+2. Job 2 takes 4 days to complete, with a penalty of d+7. Finally, job 3 takes 5 days to complete, with a penalty of 2d-4.

In this situation, the best schedule for Ramu is to complete the jobs in the sequence 1, 3, 2, for which the maximum penalty across the three jobs is 19.

Input format

The first line of input is a single integer M, the number of pending jobs. This is followed by M lines of input, each consisting of four integers. In line i+1, 1 ≤ i ≤ M, the first integer represents the number of days it takes to finish job i, and the next three integers are the coefficients a_i, b_i and c_i that determine the penalty for job i.

Output format

The output should be a single integer denoting the maximum penalty across all jobs in the optimal schedule for Ramu.

Test Data:

You can assume that 1 ≤ M ≤ 500,000. In 50% of the cases, 1 ≤ M ≤ 5000. For all jobs i and all days d, the penalty a_i d² + b_i d + c_i always fits in a long long integer (8 bytes).

Example:

Here is the sample input and output corresponding to the example discussed above.

Sample Input

Sample Output