Content：
English

Chinese(TW)
Your company, Archived Collections Management (ACM), runs the largest library system in the city. Each branch within the library system is numbered 1, 2, · · ·, M . Users are allowed to borrow books from one branch and return in another. After several years of running the system, however, the books are scattered in the branches. Thus, it becomes harder and harder for users to locate the books they want.
Getting more and more complaints from the users, your manager thought that he needed to start reforming the library system. He knew that each book is labeled with a barcode, which is a unique positive integer with value less than 100000. He then called you, and issued a simple command, “Starting next Monday, I want books with smaller barcode to be in branches of smaller or equal numbers. Do you understand?” You carefully asked, “Sir, do you mean that if book A is of barcode 5 and B is of barcode 3, and if we put book A in branch 2, then we can only put B in either branch 2 or 1?” He replied, “Exactly! Now you have an hour to calculate the amount of budget you need.”
After getting the command, you start thinking, “Let me compute the minimum required budget ﬁrst, and maybe I could ask the manager for a bit more.” You know that each branch can hold as many books as needed. You also know that before next Monday, you can only afford to move books from one branch to another directly, without going through any other branches. In addition, your secretary has given you a table that contains the cost c_{ij} for moving one book from branch i to branch j . Intuitively, the cost of moving K_{ij} books from branch i to branch j is simply K_{ij} · c_{ij} . Now, you should start writing a program for computing the minimum required budget before replying your manager.
1. The number of books N satisﬁes 1 ≤ N ≤ 99999; the number of branches M satisﬁes 1 ≤ M ≤ 32.
2. The barcode on each book is a unique integer between 1 and 99999.
3. Each cost c_{ij} is an integer; 1 ≤ c_{ij} ≤ 16 for i ≠ j ; c_{ij} = 0 for i = j.
Input：
Output：
Sample Input：
2 3 3 0 1 2 1 0 1 2 1 0 1 3 3 1 2 2 4 3 0 1 2 3 1 0 1 4 2 2 0 4 3 1 1 0 1 10 4 100 2 2
Sample Output ：
2 1
Hint
：
Author
：
C 
C++ 
JAVA 
PASCAL 

13737. tommy790506 (376ms, 17096KB, 1793B) 
51271. toi_201315 (272ms, 2296KB, 721B) 
