﻿ Fuzhou University OnlineJudge ﻿
Problem 1659 Project management

## Problem Description

Software project management is an important issue in software project planning. How to arrange people to make more benefits is a big headache for project manager. Now, the project manager turn to you for help.
There are N people in his project team, project manager will list out all the possible combinations of these N people and their combination benefits make to the project team.
A project team can be divided into several small project teams. The total benefits of the project team are the sum of the small project teams’s benefits.
We should note that：
• every people will be used, or someone will lose job，--！；
• one people can only be arranged to one team.
Please help project manager to arrange people reasonably，so that the total benefits of the project team will be maximum.

## Input

There are multiple test cases. For each case, the first line is an positive integer N（1≤N≤15）, indicating the number of people in a project team. Their labels are 1, 2, 3 … , n respectively. There are N lines followed. In the i-th line， there will be C(N,i) integers, giving out the benefits of the all combinations of i people out of N people in lexicographic order.
For example, when N = 4 and i = 2, there are C(4,2)=6 combinations（The combination of 2 people out of 4 people are （1,2）、(3,4)、（1,3）、(2,4）、(1,4) and (2,3) ). So the third line of the case input are （1,2）、（1,3）、(1,4)、(2, 3）、 (2, 4) and (3,4)’s combination benefits respectively) .

## Output

For each test, output an integer, indicating the maximum total benefits that the project team can make.

## Sample Input

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

12

## Hint

```one of the best arrangement is: （1，2）、（3）、（4）
```

## Source

FOJ月赛-2008年10月

Submit  Back  Status  Discuss
﻿