No.914 Omiyage

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 172
作問者 : ningenMeningenMe / テスター : tarattata1tarattata1
1 ProblemId : 2842 / 出題時の順位表

問題文

くる君は$N$ヵ国をめぐる旅行をすることにしました。
全ての国で$M$種類のおみやげがあり、国$i$でのおみやげの値段はそれぞれ$A_{i,1},A_{i,2},\dots,A_{i,M}$円です。
くる君は旅行の記念にそれぞれの国でおみやげを買いたいと思っています。
しかし所持金が$K$円しかなかったため、それぞれの国で必ず$1$つだけおみやげを買うことにしました。
できるだけお金を使ったとき、いくらのお金が残るでしょうか?

入力

$N\ M\ K$
$A_{1,1}\ A_{1,2}\ \dots\ A_{1,M}$
$A_{2,1}\ A_{2,2}\ \dots\ A_{2,M}$
$\vdots$
$A_{N,1}\ A_{N,2}\ \dots\ A_{N,M}$

入力は全て整数である
$1 \le N,M \le 10$
$1 \le K \le 500$
$1 \le A_{i,j} \le 50\ (1 \le i \le N,1 \le j \le M)$
$A_{i,j} < A_{i,j+1}\ (1 \le i \le N,1 \le j \le M-1)$

出力

残ったお金の値を1行で出力してください。もし1ヵ国でもおみやげを買えない国がある場合は$-1$を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3 2 10
1 2
4 5
3 6
出力
0

国$1$で$2$円、国$2$で$5$円、国$3$で$3$円使うことで合計$10$円使うことができ、残るお金は$0$円です。

サンプル2
入力
2 3 5
1 3 4
5 8 10
出力
-1

おみやげを買えない国が出てくるため$-1$を出力します。

サンプル3
入力
4 3 15
1 11 21
2 12 22
3 13 23
4 14 24
出力
5

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。