[ZJOI2010] 任务安排

题目描述

小 Y 最近遇到了一个棘手的问题。她有两项任务需要完成,其中第一项任务是重复操作 $1$(下文称作 op1)共 $S_1$ 次,第二项任务是重复操作 $2$(下文称作 op2)共 $S_2$ 次。为了完成这些任务,小 Y 雇佣了 $N$ 名工人。其中,第 $i$ 个工人完成 op1 所需时间为 $T_{1,i}$,完成 op2 所需时间为 $T_{2,i}$。每个 op1 和 op2 都只能被一名工人完成,每名工人在任意时刻都只能做一项工作。 所有的工人从第 $0$ 秒开始工作。每当一个工人开始执行一项操作(op1 或 op2),他必须一直执行下去直到完成而不能被打断。我们记第一项任务完成的时间为 $E_1$,第二项任务完成的时间为 $E_2$,你的任务就是安排这些工人的工作,使得 $E_1+E_2$ 最小。

输入输出格式

输入格式


输入文件的第一行包含一个整数 $T$,表示输入文件中数据的组数。 每个测试数据的第一行包含三个整数 $N,S_1,S_2$,含义如上文所述。 接下来的 $N$ 行每行包含两个整数 $T_{1,i},T_{2,i}$,分别表示第 $i$ 个工人完成 op1 和 op2 所需的时间。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

100
162
84
41

说明

### 样例说明 第一组数据中,唯一的工人首先执行 $2$ 次 op1,在第 $20$ 秒完成任务一 $(E_1=20)$。然后执行 $2$ 次 op2,在第 $80$ 秒完成任务二 $(E_2=80)$。因此答案为 $20+80=100$。 第二组数据中,工人 $\#1$ 连续执行 $5$ 次 op1,在第 $50$ 秒完成任务一 $(E_1=50)$,工人 $#2$ 执行 $7$ 次 op2,在第 $112$ 秒完成任务二 $(E_2=112)$。因此答案为 $50+112=162$。 第三组数据和第二组数据类似。 第四组数据中,工人 $\#2$ 首先连续执行 $6$ 次 op2,在第 $18$ 秒完成任务二 $(E_2=18)$。于此同时,工人 $#3$ 执行 $3$ 次 op1,同样在第 $18$ 秒完成。此时还需要执行一次 op1,因此让工人 $#2$ 去执行最后一次 op1,在第 $23$ 秒完成任务一 $(E_1=23)$ 、因此答案为 $18+23=41$。 ### 数据范围及约定 对于 $100\%$ 的数据,$1 \le T \le 7$,$1 \le N \le 100$,$1 \le S_1,S_2 \le 7$,$1 \le T_{1,i},T_{2,i} \le 10^6$。