Maximize Performance
Time Limit: 2 sec
Memory Limit: 256 MB
Attempts: 0
Accuracy: 0.00%
Author: Akashdeep Goel
After Virat Kohli, it’s time for India to think about it’s bowlers. The team selector visits the MRF Pace academy in Chennai.
There are a total of n bowlers in the academy who are described by the number of overs they can bowl in a day. Let this be denoted by Oi. Owing to fatigue, there are lower and upper limits Li and Ri for every bowler, Oi (both inclusive). The performance of a bowler is judged by a metric which is defined differently for every bowler by the expert. This metric is a quadratic function and performance is evaluated as fi(Oi) where fi is the function for ith bowler.
There are certain relations like Ou<= Ov + d, where u and v are different bowlers and d is an integer.
The coach at the Academy wants to show that his academy is performing good, so maximize the total output of bowlers for him.
Input
The first line of input contains integer t denoting number of testcases.
The first line of each testcase contains two integers n and m, the number of bowlers and the number of relations.
Then follow n lines, each containing three integers pi, qi and ri, the coefficients of the quadratic function fi(x). That is, fi(x) = pix2 + qix +ri
Then follow n lines, each containing li and ri.
Then follow m lines, each containing three integers ui, vi and di, describing a relation.
Output
For each test case, print the maximum output of all bowlers in the academy in separate line. If there is no possible combination that satisfies the constraints, output "-1".
Constraints
1<=n<=50
0<=m<=100
|pi|<=10, and |qi|,|ri|<=1000
-100<=li<=ri<=100
1<=ui,vi<=n, ui is different from vi, and |di|<=200
Example
Input:
1
3 3
0 1 0
0 1 1
0 1 2
0 3
1 2
-100 100
1 2 0
2 3 0
3 1 0
Output:
9
ID
SUBMITTED AT
STATUS
LANGUAGE
TIME
MEMORY USED
USER
TIME
STATUS
LANGUAGE
TIME
MEMORY USED
4 years ago
cpp
0.13 sec
660 KB
4 years ago
cpp
0.00 sec
0 KB
4 years ago
cpp
0.11 sec
660 KB
4 years ago
cpp
0.07 sec
64 KB
4 years ago
cpp
0.11 sec
660 KB
4 years ago
cpp
0.11 sec
660 KB
4 years ago
cpp
0.11 sec
660 KB
4 years ago
cpp
0.26 sec
656 KB
4 years ago
cpp
0.11 sec
660 KB
4 years ago
cpp
0.11 sec
660 KB
4 years ago
cpp
0.11 sec
528 KB
4 years ago
cpp
0.11 sec
660 KB