任务安排

题目描述:

小Y最近遇到了一个棘手的问题。她有两项任务需要完成，其中第一项任务是重复操作1(op₁)S₁次，第二项任务是重复操作2(op₂)S₂次。为了完成这些任务，小 Y雇佣了N名工人。其中，第i个工人完成op₁所需时间为T_1,i，完成op₂所需时间为T_2,i。每个op₁和op₂都只能被一名工人完成，每名工人在任意时刻都只能做一项工作。

         所有的工人从第0秒开始工作。每当一个工人开始执行一项操作(op₁或op₂)，他必须一直执行下去直到完成而不能被打断。我们记第一项任务完成的时间为E₁，第二项任务完成的时间为E₂，你的任务就是安排这些工人的工作，使得E₁+E₂最小。

输入格式:

第一行包含一个整数T，表示输入文件中数据的组数。

每个测试数据的第一行包含三个整数N S₁S₂，含义如上文所述。

 接下来的N行每行包含两个整数T_1,I、T_2,i，分别表示第i个工人完成op₁和op₂所需的时间。

输出格式:

包含T行，每行只有一个整数，表示你找到的E₁+E₂的最小值。

样例输入:

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

提示:

样例说明

       第一组数据中，唯一的工人首先执行2次op₁，在第20秒完成任务一(E₁=20)。然后执行2次op₂，在第80秒完成任务二(E₂=80)。因此答案为20+80=100。

       第二组数据中，工人#1连续执行5次op₁，在第50秒完成任务一(E₁=50)，工人#2执行7次op₂，在第112秒完成任务二(E₂=112)。因此答案为50+112=162。

       第三组数据和第二组数据类似。

       第四组数据中，工人#2首先连续执行6次op_2­，在第18秒完成任务二(E₂=18)。于此同时，工人#3执行3次op₁，同样在第18秒完成。此时还需要执行一次op₁，因此让工人#2去执行最后一次op₁，在第23秒完成任务一(E₁=23)、因此答案为18+23=41。

 

数据规模

       100%的数据中，1<=T<=7，1<=n<=100，1<=s1,s2<=7，1<=T_1,i，T_2,i<=1,000,000。

时间限制: 2000ms
空间限制: 256MB

---

来源: 浙江省选2010day2t2