題目

你有 n 臺機(jī)器編號為 1~n，每臺都需要完成完成一項(xiàng)工作，機(jī)器經(jīng)過配置后都能完成獨(dú)立完成一項(xiàng)工作。

假設(shè)第 i 臺機(jī)器你需要花 B 分鐘進(jìn)行設(shè)置，然后開始運(yùn)行，J 分鐘后完成任務(wù)。

現(xiàn)在，你需要選擇布置工作的順序，使得用最短的時(shí)間完成所有工作。

注意，不能同時(shí)對兩臺進(jìn)行配置，但配置完成的機(jī)器們可以同時(shí)執(zhí)行他們各自的工作。

輸入描述：

第一行輸入代表總共有 M 組任務(wù)數(shù)據(jù)（1<M<=10）。

每組數(shù)第一行為一個(gè)整數(shù)指定機(jī)器的數(shù)量 N（0<N<=1000）。

隨后的 N 行每行兩個(gè)整數(shù)，第一個(gè)表示 B（0<=B<=10000），第二個(gè)表示 J（0<=J<=10000）。

每組數(shù)據(jù)連續(xù)輸入，不會用空行分隔。各組任務(wù)單獨(dú)計(jì)時(shí)。

輸出描述：

對于每組任務(wù)，輸出最短完成時(shí)間，且每組的結(jié)果獨(dú)占一行。例如，兩組任務(wù)就應(yīng)該有兩行輸出。

示例1? 輸入輸出示例僅供調(diào)試，后臺判題數(shù)據(jù)一般不包含示例

輸入

1

1

2 2

輸出

4

解釋：

第一行1為一組任務(wù)，第二行1代表只有一臺機(jī)器，第三行表示該機(jī)器配置需2分鐘，執(zhí)行需2分鐘。

示例2? 輸入輸出示例僅供調(diào)試，后臺判題數(shù)據(jù)一般不包含示例

輸入

2

2

1 1

2 2

3

1 1

2 2

3 3

輸出

4

7

解釋：

第一行2代表兩組任務(wù)，

第二行2代表第一組任務(wù)有2個(gè)機(jī)器，

第三行1 1代表機(jī)器1配置需要1分運(yùn)行需要1分，

第四行2 2代表機(jī)器2配置需要2分運(yùn)行需要2分，

第五行3代表第二組任務(wù)需要3個(gè)機(jī)器，

第6-8行分別表示3個(gè)機(jī)器的配置與運(yùn)行時(shí)間。

Java 實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/128139721

Python實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/128383243

C++ 實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/127222061

JavaScript實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/131556699

C實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/130516651