10662 - The Wedding

The Wedding

Background

Felix 和 Leti 即將要結婚了，每個人正準備給他們這對新人禮物，但是他們的預算並不多，他們想要讓他們有一個不錯的餐廳，以及在一個高級旅館睡了一晚，接著再環遊世界的蜜月旅行。

希望能得到最便宜的價格包含上述的行程內容，湊出旅行、餐廳、旅館的行程。

The Problem

我們必須找到最便宜的 旅行社－餐廳－旅館 的組合，但並不是每種組合都可以。

The Input

每組測資的格式如下：

• 第一行有三個整數 T, R, H，分別表示旅行社、餐廳、旅館的數量。
  T < 20, R < 20 , H < 20.  且三者的編號皆從 0, 1, 2, ...
  
• 接下來會有  T+R+H  行，分別有三個區塊：
  • 前 T 行，每行上有 R+1 個整數，第一個整數表示該旅行社的花費，而接下來 R 個整數表示 cell(i,j)，表示旅行社(i)是否可以跟餐廳(j)搭配，cell(i,j) = 0 表示可以，反之不行。
    
  • 接下來 R 行，每行上有 H+1 個整數，第一個整數表示該餐廳的花費，而接下來 H 個整數表示 cell(i,j)，表示餐廳(i)是否可以跟旅館(j)搭配，cell(i,j) = 0 表示可以，反之不行。
    
  • 接下來 H 行，每行上有 T+1 個整數，第一個整數表示該旅館的花費，而接下來 T 個整數表示 cell(i,j)，表示旅館(i)是否可以跟旅行社(j)搭配，cell(i,j) = 0 表示可以，反之不行。

The Output

對於每組輸出格式如下：

T R H:P

分別表示旅行社編號、餐廳編號、旅館編號以及最便宜的花費。
如果不存在任何組合，則輸出：Don't get married!

如果有多組可能，任何一組都可以。

Sample Input

2 2 2
12 0 0
1 1 1
34 0 0
3 1 1
21 1 0
2 1 0
2 2 2
12 0 0
1 0 0
34 0 0
3 0 0
21 0 0
2 0 0
5 5 6
970 0 1 1 1 0 
856 0 0 0 0 0 
1290 1 0 0 1 0 
1361 0 0 1 0 0 
82 0 0 0 0 1 
1182 0 0 0 1 1 0 
450 0 1 1 0 0 1 
895 0 0 1 0 1 1 
1865 0 1 0 0 1 1 
183 1 1 1 1 1 0 
252 1 1 1 0 1 
1813 1 0 0 1 1 
1429 0 0 1 0 0 
1522 1 1 1 0 0 
1762 0 0 1 0 1 
1946 0 1 0 0 0 

Sample Output

Don't get married!
1 1 1:6
4 1 3:2054