TopCoder

User's AC Ratio

100.0% (8/8)

Submission's AC Ratio

75.0% (12/16)

Description

眼睛看不到的一個巨大趨勢,雖然我不知道那該叫做世界還是宇宙,但我跟你都是這巨大趨勢中的一個小東西

也就是全中的一,但必須有這些一聚集在一起,才會行成全,這個世界依循著一個我們無法想像的巨大法則而

流動著。了解那個趨勢,並且進行分解與再築構,這就是『鍊金術』-- 鋼之鍊金術師

  在這個世界的規則是這樣的:

  #1有種東西叫做價值,有形也好無形也好,價值就只是個價值,越高越好。

  #2任兩物質融合後,一定會有一個物質被取代,而不會產生第三種物質。

  在你眼前有著n樣物質,以及兩張紙張,上面各有一個n*n 的表格

  分別是:

  #1當兩個物質融合後所獲得的價值是多少

  #2當兩個物質融合後會是哪個物質留下(另個物質會被取代掉)

  身為一個稱職的鍊金術師,你要怎樣融合使獲得的價值會最高呢?!

Input Format

包含多組測試資料,資料以EOF最為結束。(測試資料不超過10組)

每組測字資料第一行為一個數字n (1≦n≦15),接下來有兩個n*n的表格

分別代表:

  #1當兩個物質融合後所獲得的價值是多少

  #2當兩個物質融合後會是哪個物質留下(另個物質會被取代掉)

Output Format

輸出可獲得的價值最高是多少。

Sample Input

3
1 2 3
2 2 3
3 3 3
0 0 2
0 1 2
2 2 2
5
1 7 4 0 9
7 4 8 8 2
4 8 4 5 5
0 8 5 1 7
9 2 5 7 1
0 0 2 0 4
0 1 2 3 1
2 2 2 3 2
0 3 3 3 4
4 1 2 4 4

Sample Output

6
29

Hints

兩物質混合沒有先後關係,固你可以假設表格都是呈現對稱的。
也就是說兩張表格都是:table[a][b]==table[b][a] 這種關係。

※2008/07/27 範例輸入修正 by hallogameboy,感謝 akira,shik。

Problem Source

原TIOJ1390 / 快樂暑假營第三次練習比賽。
Problem Setter:ggm。

Subtasks

For Testdata: 0 ~ 0, Score: 25
For Testdata: 1 ~ 1, Score: 25
For Testdata: 2 ~ 2, Score: 25
For Testdata: 3 ~ 3, Score: 25
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 65536
1 3000 65536 65536
2 3000 65536 65536
3 3000 65536 65536