提示: 欢迎访问OurACM平台。
Problem 1659 Project management

Accept: 59    Submit: 124
Time Limit: 2000 mSec    Memory Limit : 32768 KB

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

Sample Output

12

Hint

one of the best arrangement is: (1,2)、(3)、(4)

Source

FOJ月赛-2008年10月

Submit  Back  Status  Discuss