Preparing NOJ

Getting a good bonus!

1000ms 65536K

Description:

Edward is the project manager of Cha-Cha-Cha (Sam-Cha) Software Company International gets many software projects to develop from SIPA. Each software project carries one score, plus a bonus if submitted within a specified number of weeks. The deadline to get the bonus and the number of bonus scores are different for each project. For example, if a project has a deadline of 6 weeks and carries bonus 10 scores, then it earns 10 bonus scores if it is submitted before the end of the 6th week. Each project takes exactly one week to complete. For instance, suppose there are seven projects with deadlines and bonuses as follows:

Project number

1

2

3

4

5

6

7

Deadline for bonus

page2image17960 page2image18280

1

page2image19504

1

page2image20568

3

page2image21632

3

page2image22696

2

page2image23760

2

page2image24824

6

Bonus score

page2image27472 page2image27792

6

page2image28720 page2image29040
page2image29512

7

page2image30440
page2image30912

3

page2image31840
page2image32312

1

page2image33240
page2image33712

4

page2image34640
page2image35112

5

page2image36040
page2image36512

1

page2image37440



The maximum bonus score is 16, which can be achieved by completing the projects in the sequence 2,6,3,1,7,5,4.

Note that there are also other sequences that achieve the same score. Your task is to find a schedule to complete all software projects so as to maximize bonus score. 


Input:

The first line contains an integer N (1  N  50) which determines number of the test cases. The following line is to indicate M (1  M  24), where M is the number of software projects. This is followed by M lines, each containing two integers. The first integer is the deadline for the i thproject and the second integer is the bonus score assigned to the ith projects, (1  i  M) 


Output:

For each test case, print out the maximum score that can be obtained. 


Sample Input:

2

1 6 
1 7 
3 2 
3 1 
2 4 
2 5 
6 1 
4
2 10 
1 9 
2 7 
7 1

Sample Output:

15
20

Note:

用于NUPT ACM 2010 Personal Ranking Contest 5

本题由旧版NOJ导入,来源:ACM-ICPC Thailand Southern Area Programming Contest 2010

Info

NOJ

Provider NOJ

Code NOJ1459

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet