시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 79 | 53 | 51 | 71.831% |
You are M, the head of the intelligence agency which employs N spies with codenames from 1 to N.
Each of the spies has been assigned a different country and obtained an important piece of informationthere. Your task is the following:
Find the minimum total price of preparing and executing this assignment.
The first line of input contains the positive integer N, the number of spies (2 ≤ N ≤ 1000).
Each of the following N lines contains N positive integers not exceeding 106. The number in row k and column m represents the price of a meeting between spies k and m and, of course, equals the number in row m and column k (for k = m the number will be 0).
The following line contains N positive integers Mk (1 ≤ Mk ≤ 106), the prices of sending each spy on the assignment, in order for spies 1, 2, ..., N.
The first and only line of output must contain the required minimum total price.
3 0 6 9 6 0 4 9 4 0 7 7 7
17
3 0 17 20 17 0 10 20 10 0 15 9 12
34
5 0 3 12 15 11 3 0 14 3 20 12 14 0 11 7 15 3 11 0 15 11 20 7 15 0 5 10 10 10 10
28
Clarification of the first example: We will organize meetings between spies 1 and 2, then 2 and 3, and send spy 2 on the assignment.
Clarification of the second example: We will organize a meeting between spies 2 and 3, and send spies 1 and 2 on the assignment.
Clarification of the third example: We will organize meetings between spies 2 and 4, then 1 and 2, then 3 and 5, and send spies 1 and 3 (or 1 and 5) on the assignment.