Back to Category
d013: [08.12] B - Organizing Books
Keyword: Dynamic Programming, 林軒田, PTC 2008

Difficulity: 4 | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 37 Times | Submit :133 Times | Clicks : 1806
Accepted : 25 Users | Submit : 30 Users | Accepted rate : 83%
Time Limit :3000 ms | Memory Limit : 64000 KBytes
Update : 2010-07-20 21:02

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 first, 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 cij for moving one book from branch i to branch j . Intuitively, the cost of moving Kij books from branch i to branch j is simply Kij · cij . Now, you should start writing a program for computing the minimum required budget before replying your manager.

Technical Specification

1. The number of books N satisfies 1 ≤ N ≤ 99999; the number of branches M satisfies 1 ≤ M ≤ 32.
2. The barcode on each book is a unique integer between 1 and 99999.
3. Each cost cij is an integer; 1 ≤ cij ≤ 16 for ij ; cij = 0 for i = j.

Input:

The first line of the input file contains an integer indicating the number of test cases to follow. The first line of each test case contains two integers M and N separated by a space. Then, the i-th following line contains M integers separated by spaces, and the j-th of those integers is cij . After M of those lines, each of the following N lines contains two integers m and b separated by a space, where m means the current location of the book and b means the barcode on the book.

Output:

For each test case, output the minimum required budget in a line.

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
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 :

click here to download the problem solving hint

Author :

林軒田, PTC 2008

  Solve it!   Status Forum

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

Program running time may be affected by various factors. Check server system environment information here