#P2608. [ZJOI2010] 任务安排
[ZJOI2010] 任务安排
题目描述
小 Y 最近遇到了一个棘手的问题。她有两项任务需要完成,其中第一项任务是重复操作 (下文称作 op1)共 次,第二项任务是重复操作 (下文称作 op2)共 次。为了完成这些任务,小 Y 雇佣了 名工人。其中,第 个工人完成 op1 所需时间为 ,完成 op2 所需时间为 。每个 op1 和 op2 都只能被一名工人完成,每名工人在任意时刻都只能做一项工作。
所有的工人从第 秒开始工作。每当一个工人开始执行一项操作(op1 或 op2),他必须一直执行下去直到完成而不能被打断。我们记第一项任务完成的时间为 ,第二项任务完成的时间为 ,你的任务就是安排这些工人的工作,使得 最小。
输入格式
输入文件的第一行包含一个整数 ,表示输入文件中数据的组数。
每个测试数据的第一行包含三个整数 ,含义如上文所述。
接下来的 行每行包含两个整数 ,分别表示第 个工人完成 op1 和 op2 所需的时间。
输出格式
输出文件包含 行,每行只有一个整数,表示你找到的 的最小值。
4
1 2 3
10 20
3 5 7
10 20
15 16
17 18
4 3 6
10 12
8 9
16 11
13 20
4 4 6
7 12
5 3
6 5
1000000 1000000
100
162
84
41
提示
样例说明
第一组数据中,唯一的工人首先执行 次 op1,在第 秒完成任务一 。然后执行 次 op2,在第 秒完成任务二 。因此答案为 。
第二组数据中,工人 连续执行 次 op1,在第 秒完成任务一 ,工人 #2 执行 次 op2,在第 秒完成任务二 。因此答案为 。
第三组数据和第二组数据类似。
第四组数据中,工人 首先连续执行 次 op2,在第 秒完成任务二 。于此同时,工人 #3 执行 次 op1,同样在第 秒完成。此时还需要执行一次 op1,因此让工人 #2 去执行最后一次 op1,在第 秒完成任务一 、因此答案为 。
数据范围及约定
对于 的数据,,,,。