TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

在小風國裡,一共有 m 座城市,編號為 0,1,,m1,小風手上有 n 臺伺服器,編號為 0,1,,n1Qi,j 代表第 i 臺伺服器需要傳送到第 j 座城市中的用戶流量。由於城市間傳送資料需要錢,小風命令工程師們規劃伺服器安裝在不同城市的最佳方案,如果城市 u 之中全部伺服器傳送至城市 v 的流量總共為 f ,所需的花費為:

  • 若為同城市內互打 u=v,則每單位的流量花費 1 元。
  • 若為跨城市傳送 uv,不超過 1000 單位的流量每單位 3 元,超過 1000 單位的流量每單位 2 元。

如果一座城市 u 有多座伺服器都要傳送資料至城市 v,則會將所有伺服器的資料量加總再計算花費。工程師們一共列出了 k 種方案,每種方案可以用 c=(c0,c1,,cn1) 來表示,其中 ci 代表第 i 臺伺服器座落的城市。請幫小風計算出哪一種方案的花費最少。

Input Format

輸入第一行包含三個正整數 n,m,k(1n,m,k50)
接下來的 n 行,每一行有 m 個數字,第 i 行的第 j 個數字代表流量 Qi,j(1Qi,j1000)
接下來的 k 行,每一行有 k 個數字 c0,c1,,cn1,代表工程師設計的其中一種方案。

Output Format

請輸出一個整數代表這些方案中的最小花費。

Sample Input 1

2 3 3
30 23 23
5 25 3
0 0
0 1
0 2

Sample Output 1

217

Sample Input 2

3 4 5
500 400 800 200
500 400 100 600
450 420 800 790
0 0 0
0 1 2
0 2 2
2 1 2
1 1 1

Sample Output 2

13470

Hints

Problem Source

APCS 歷屆

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~12 n=1,k=1 20
3 2~23 n=1 30
4 0~34 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 4
1 1000 524288 65536 1 4
2 1000 524288 65536 2 3 4
3 1000 524288 65536 2 3 4
4 1000 524288 65536 2 3 4
5 1000 524288 65536 2 3 4
6 1000 524288 65536 2 3 4
7 1000 524288 65536 2 3 4
8 1000 524288 65536 2 3 4
9 1000 524288 65536 2 3 4
10 1000 524288 65536 2 3 4
11 1000 524288 65536 2 3 4
12 1000 524288 65536 2 3 4
13 1000 524288 65536 3 4
14 1000 524288 65536 3 4
15 1000 524288 65536 3 4
16 1000 524288 65536 3 4
17 1000 524288 65536 3 4
18 1000 524288 65536 3 4
19 1000 524288 65536 3 4
20 1000 524288 65536 3 4
21 1000 524288 65536 3 4
22 1000 524288 65536 3 4
23 1000 524288 65536 3 4
24 1000 524288 65536 4
25 1000 524288 65536 4
26 1000 524288 65536 4
27 1000 524288 65536 4
28 1000 524288 65536 4
29 1000 524288 65536 4
30 1000 524288 65536 4
31 1000 524288 65536 4
32 1000 524288 65536 4
33 1000 524288 65536 4
34 1000 524288 65536 4