#P2608. [ZJOI2010] 任务安排

[ZJOI2010] 任务安排

题目描述

小 Y 最近遇到了一个棘手的问题。她有两项任务需要完成,其中第一项任务是重复操作 11(下文称作 op1)共 S1S_1 次,第二项任务是重复操作 22(下文称作 op2)共 S2S_2 次。为了完成这些任务,小 Y 雇佣了 NN 名工人。其中,第 ii 个工人完成 op1 所需时间为 T1,iT_{1,i},完成 op2 所需时间为 T2,iT_{2,i}。每个 op1 和 op2 都只能被一名工人完成,每名工人在任意时刻都只能做一项工作。

所有的工人从第 00 秒开始工作。每当一个工人开始执行一项操作(op1 或 op2),他必须一直执行下去直到完成而不能被打断。我们记第一项任务完成的时间为 E1E_1,第二项任务完成的时间为 E2E_2,你的任务就是安排这些工人的工作,使得 E1+E2E_1+E_2 最小。

输入格式

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

每个测试数据的第一行包含三个整数 N,S1,S2N,S_1,S_2,含义如上文所述。

接下来的 NN 行每行包含两个整数 T1,i,T2,iT_{1,i},T_{2,i},分别表示第 ii 个工人完成 op1 和 op2 所需的时间。

输出格式

输出文件包含 TT 行,每行只有一个整数,表示你找到的 E1+E2E_1+E_2 的最小值。

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

提示

样例说明

第一组数据中,唯一的工人首先执行 22 次 op1,在第 2020 秒完成任务一 (E1=20)(E_1=20)。然后执行 22 次 op2,在第 8080 秒完成任务二 (E2=80)(E_2=80)。因此答案为 20+80=10020+80=100

第二组数据中,工人 #1\#1 连续执行 55 次 op1,在第 5050 秒完成任务一 (E1=50)(E_1=50),工人 #2 执行 77 次 op2,在第 112112 秒完成任务二 (E2=112)(E_2=112)。因此答案为 50+112=16250+112=162

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

第四组数据中,工人 #2\#2 首先连续执行 66 次 op2,在第 1818 秒完成任务二 (E2=18)(E_2=18)。于此同时,工人 #3 执行 33 次 op1,同样在第 1818 秒完成。此时还需要执行一次 op1,因此让工人 #2 去执行最后一次 op1,在第 2323 秒完成任务一 (E1=23)(E_1=23) 、因此答案为 18+23=4118+23=41

数据范围及约定

对于 100%100\% 的数据,1T71 \le T \le 71N1001 \le N \le 1001S1,S271 \le S_1,S_2 \le 71T1,i,T2,i1061 \le T_{1,i},T_{2,i} \le 10^6