# Picnic

Time Limit : 2 sec, Memory Limit : 262144 KB

# Problem G: Picnic

## Problem

͂悢}CdwZ̉̓łB}CdwZɒʂŃAŷ݂܂薾َ̂q𔃂YĂƂɋCÂB N͉őyނ߁Aَqɂ肽B

N͂ꂳ񂩂$X$~̂Ăَq𔃂ɍsBAwZ̃[ŉɎĂَq̍vz$Y$~܂łƌ܂ĂA$Y$~Ƃَq͑SĐ搶ɎグĂ܂B

N̏Zފwɂ$N$̒Aeɂ1̑ʉَqBeɂ1$N$̔ԍUĂAN͒1ɏZłB eʉَqł͂َ̂qĂA1̒liA1ƂɂN閞x܂ĂBAeَq̍݌ɐɂ͌肪B ܂AN2̒̊ԂړƂʋ@ւ𗘗p邽߁A$i$璬$j$֒ڈړɂ$d_{i,j}$~B

ŏAN͒1ɂBN͈ړɂp̍vƔَq̒li̍v̘a$X$~ȓŁAAَq̒li̍v$Y$~ȓɂȂ悤ɂَq𔃂ɍsBŌɂ͒1ɓĂKvBNَ͔q̖x̍vł邾傫Ȃ悤ɂBNœKȍsƂ̖x̍v߂B

## Input

͈͂ȉ̌łׂĐŗ^B

$N$ $X$ $Y$
1̑ʉَq̏
2̑ʉَq̏
...
$N$̑ʉَq̏
$d_{1,1}$ $d_{1,2}$ ... $d_{1,N}$
$d_{2,1}$ $d_{2,2}$ ... $d_{2,N}$
...
$d_{N,1}$ $d_{N,2}$ ... $d_{N,N}$

1sڂɒ̐$N$Ə$X$Aَq𔃂߂ɎgƂłz$Y$󔒋؂ŗ^B
2sڂ$N$̊eʉَq̏񂪗^B
$N$s$N$ɒ$i$ƒ$j$𒼐ڍs邽߂ɕKvȋz$d_{i,j}$󔒋؂ŗ^B

ȇʉَq͈̏ȉ̌ŗ^B

$K$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
...
$a_K$ $b_K$ $c_K$

1sڂɂ̑ʉَqŔĂ邨َq̎ނ̐$K$^B$K$sɂَq1̒li$a_i$A1̖x$b_i$A݌ɐ$c_i$󔒋؂ŗ^B

## Constraints

͈͂ȉ̏𖞂B

• $1 \leq N \leq 14$
• $1 \leq X \leq 10000$
• $1 \leq Y \leq min(1000,X)$
• $1 \leq K \leq 300$
• $1 \leq a_i \leq 1000$
• $1 \leq b_i \leq 1000$
• $1 \leq c_i \leq 1000$
• $0 \leq d_{i,j} \leq 10000$
• $d_{i,i} = 0$

x̍v̍ől1sɏo͂B

## Sample Input 1

1 10 10
3
1 10 1
2 20 2
3 30 3
0


## Sample Output 1

100


## Sample Input 2

2 10 10
3
1 10 1
2 20 2
3 30 3
1
5 200 1
0 2
3 0


## Sample Output 2

200


## Sample Input 3

3 10 10
1
1 1 1
1
3 3 3
1
5 5 5
0 1 0
1 0 0
0 1 0


## Sample Output 3

10


## Sample Input 4

4 59 40
1
7 6 3
1
10 3 9
2
9 8 5
7 6 10
4
8 2 9
1 7 1
7 7 9
1 2 3
0 28 7 26
14 0 10 24
9 6 0 21
9 24 14 0


## Sample Output 4

34


Source: Aizu Competitive Programming Camp 2017 , Day 2, Aizu-Wakamatsu, Japan, 2017-09-19