A - Multiplication 0
Assam
2
s
1024
MB
250
点
問題文
ペンギンは $N$ 個の数列 $A_1,\ A_2,\ \ldots,\ A_N$ を持っています。各 $i\ (1 \leq i \leq N)$ について、$A_i$ の長さは $l_i$ に等しいです。
各数列から $1$ つずつ要素を取り出してその総積を取るとき、最大値はいくつになりますか？
制約
- $1 \leq N \leq 9$
- $1 \leq l_i \leq 200$
- $-100 \leq A_{i,j} \leq100$
- $A_{i,j} \neq A_{i,k}\ (j \neq k)$
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
$N$
$l_1$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,l_1}$
$l_2$
$A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,l_2}$
$\vdots$
$l_N$
$A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,l_N}$
出力
総積の最大値を出力せよ。
入力例 1
2
3
-10 2 5
4
-5 19 -9 6
出力例 1
95
$A_1$ から $5$ を、$A_2$ から $19$ を取り出した場合に最大値を取ります。
入力例 2
3
2
-11 -8
6
-99 -8 -24 -4 -3 -53
3
-5 -3 -8
出力例 2
-72
答えは負にもなり得ます。
入力例 3
9
10
53 90 3 -67 -64 1 100 9 62 -11
4
-12 52 -42 -29
7
93 77 74 13 -49 -98 91
9
-81 -69 -100 5 -24 -74 -22 77 80
2
27 72
1
-23
1
4
7
19 33 34 -90 -39 -37 40
8
75 60 -56 -65 11 -35 -27 55
出力例 3
2278523520000000
答えが $32\ \text{bit}$ 整数型に収まらない場合があります。