1560 - Two Machines Scheduling

Time Limit : 2 Second

Memory Limit : 128 MB

Submission: 36

Solved: 5

Description
The two machines scheduling is the process of assigning a group of tasks to two machines.



Given n tasks, each task i associates with t1i and t2i the processing time of the task on machine 1 and machine 2, respectively.

Besides, there are values p1i and p2i that denote the preference of task i assigning to machine 1 and machine 2.

Note that machine 1 is capable to handle at most Q1 tasks while the capacity of machine 2 is Q2 (Q1+Q2>=n).



Your job is to determine an optimal assignment of tasks to two machines such that the total processing time is minimal.

If there exist a tie, the total preference should be maximal.

Input
       The input file may consist of multiple test cases.

       For each test case, the first line is the number of tasks n, followed by the capacities of two machines Q1 and Q2. The next n lines each line i (1<=i<=n) contains four integers t1i, t2i, p1i, p2i, which are defined by the problem description. n<=100,000 and each of the integer t1i, t2i, p1i, p2i is no greater than 100.

Output
       For each test case, output two integers T and P. T corresponds to the minimal processing time of all tasks on two machines and P corresponds to the maximal preference.

sample input
3 2 2
1 1 1 1
1 2 1 2
2 1 2 1
3 2 2
1 1 1 2
1 2 1 2
2 1 2 1
sample output
3 3
3 4
hint
 
You can use this form of code to deal with several test cases.
 
while (scanf(...) != EOF)
{
//Your codes here.
}
 
or
 
while (cin >> input)
{
//your code here
}
 
source
The 6th ACM Programming Contest of HUST
© 2015 HUST ACMICPC TEAM. All Right Reserved.