Pro.ID22127 TitleHelpful papers Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22127 AC0 Submit0 Ratio- 时间&空间限制描述How time flies! Sunshine, an intelligent girl, becomes a senior student now. Recently, she is preparing for her thesis. She made a plan to read many papers, because only in this way can she master the research trends in her interesting field and form her own ideas. Now Sunshine has downloaded many papers. Every paper has only one author, and maybe some of them were written by the same person. Sunshine wants to read each author’s paper according to the time these papers were written. For example, Sunshine has five papers: P1 (written by A in 1981), P2 (written by B in 1982), P3 (written by A in 1986), P4 (written by B in 1989), P5 (written by A in 1999). Sunshine should read P1 before reading P3, P3 before reading P5, and P2 before reading P4. So all the possibility of the schedules are list here: P1 -> P3 -> P5 -> P2 -> P4 P1 -> P3 -> P2 -> P5 -> P4
P1 -> P2 -> P3 -> P5 -> P4 P2 -> P1 -> P3 -> P5 -> P4
P1 -> P3 -> P2 -> P4 -> P5 P1 -> P2 -> P3 -> P4 -> P5
P2 -> P1 -> P3 -> P4 -> P5 P1 -> P2 -> P4 -> P3 -> P5
P2 -> P1 -> P4 -> P3 -> P5 P2 -> P4 -> P1 -> P3 -> P5 What’s more, each paper has two parameters (Wi, Ti). Ti is the time of reading the paper and Wi , is an added value that is used to represent the importance of the paper. Now Sunshine asks you to give her a schedule S that Cost(S) is minimal. For schedule S(P1, P2, ..., Pn ), Cost(S) = W1*T1 + W2*(T1+T2) + W3*(T1+T2+T3) + ... + Wn*(T1+T2+...+Tn)
输入The first line of the input is a positive integer C which is the number of the test cases followed. Each test case contains two parts. The first line of the first part is a positive integer N ( 0 < N <= 100 ) which represents the number of the papers. After that, N lines are followed. The i-th line contains two positive integers Wi ( 0 < Wi <= 100 ), Ti ( 0< Ti <= 100 ) for the i-th paper. The first line of the second part is a positive integer M ( 0 < M <= 100 ) which means the number of the researchers. And the following M lines inform you the papers that were written by the researchers. The first number of the i-th line is an positive number Ai (0 < Ai <= 100) telling you the number of the papers the i-th researchers wrote. After that there are A, numbers that represent the IDs of the papers according to the time they were written. 输出Description How time flies! Sunshine, an intelligent girl, becomes a senior student now. Recently, she is preparing for her thesis. She made a plan to read many papers, because only in this way can she master the research trends in her interesting field and form her own ideas. Now Sunshine has downloaded many papers. Every paper has only one author, and maybe some of them were written by the same person. Sunshine wants to read each author’s paper according to the time these papers were written. For example, Sunshine has five papers: P1 (written by A in 1981), P2 (written by B in 1982), P3 (written by A in 1986), P4 (written by B in 1989), P5 (written by A in 1999). Sunshine should read P1 before reading P3, P3 before reading P5, and P2 before reading P4. So all the possibility of the schedules are list here: P1 -> P3 -> P5 -> P2 -> P4 P1 -> P3 -> P2 -> P5 -> P4
P1 -> P2 -> P3 -> P5 -> P4 P2 -> P1 -> P3 -> P5 -> P4
P1 -> P3 -> P2 -> P4 -> P5 P1 -> P2 -> P3 -> P4 -> P5
P2 -> P1 -> P3 -> P4 -> P5 P1 -> P2 -> P4 -> P3 -> P5
P2 -> P1 -> P4 -> P3 -> P5 P2 -> P4 -> P1 -> P3 -> P5 What’s more, each paper has two parameters (Wi, Ti). Ti is the time of reading the paper and Wi , is an added value that is used to represent the importance of the paper. Now Sunshine asks you to give her a schedule S that Cost(S) is minimal. For schedule S(P1, P2, ..., Pn ), Cost(S) = W1*T1 + W2*(T1+T2) + W3*(T1+T2+T3) + ... + Wn*(T1+T2+...+Tn)
Input The first line of the input is a positive integer C which is the number of the test cases followed. Each test case contains two parts. The first line of the first part is a positive integer N ( 0 < N <= 100 ) which represents the number of the papers. After that, N lines are followed. The i-th line contains two positive integers Wi ( 0 < Wi <= 100 ), Ti ( 0< Ti <= 100 ) for the i-th paper. The first line of the second part is a positive integer M ( 0 < M <= 100 ) which means the number of the researchers. And the following M lines inform you the papers that were written by the researchers. The first number of the i-th line is an positive number Ai (0 < Ai <= 100) telling you the number of the papers the i-th researchers wrote. After that there are A, numbers that represent the IDs of the papers according to the time they were written. Output The output of the program should consist of one line of output for each test case. The output of each test case only contains an integer which represents the minimal Cost(S). No redundant spaces are needed. Sample Input 1
7
6 3
18 6
12 6
8 5
8 4
17 8
18 10
2
4 1 2 3 4
3 5 6 7 Sample Output 1967 Source 样例输入1
7
6 3
18 6
12 6
8 5
8 4
17 8
18 10
2
4 1 2 3 4
3 5 6 7 样例输出1967 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-4 13:54 , Processed in 0.035648 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
