Problem 1: Paying the Price
, *(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*^{2} + *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
3*d*+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 2*d*-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*^{2} + *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

3 3 0 3 2 4 0 1 7 5 0 2 -4

Sample Output

19

Copyright (c) IARCS 2003-2020; Last Updated: 22 Oct 2007