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 1 1 3 3 2 2 6 Bonus score 6 7 3 1 4 5 1



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:

27 1 6 1 7 3 2 3 1 2 4 2 5 6 1 42 10 1 9 2 7 7 1

## Sample Output:

1520

## Note:

Info

Provider NOJ

Code NOJ1459

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet