B.冒险 foray

题目描述

$Introl$有$N$件生命值分别为$H_1,H_2......H_N$的盔甲。

他将通过$T$段长度分别为$M_1,M_2.....M_T$的魔法地界中的某一条去异世界冒险，其经过$M_{i,j}$时盔甲会收到$K_{i,j}$的效果，当盔甲的生命值小于等于$0$时就会破碎。

$Introl$希望通过魔法地界后盔甲仍未破碎并且他只会选择生命值最小且足够他通过该段魔法地界的盔甲。

对于每段魔法地界，存在合法方案时输出选择的盔甲的生命值，不存在合法方案时输出$-1$。

输入格式

第一行仅三个整数$N$和$T$。

第二行共$N$个整数$H_1,H_2......H_N$。

第三行共$T$个整数$M_1,M_2......M_T$。

接下来$T$行，每行$M_i$个整数$K_{i,1},K_{i,2}......K_{i,{M_i}}$

输出格式

共$T$行。

存在合法方案时输出选择的盔甲的生命值。

不存在合法方案时输出$-1$。

样例

【样例 1 输入】

3 3
100 200 300
3 3 4
-100 1000 560
-1000 2000 363
-150 100 200 -300

【样例 1 输出】

200
-1
200

数据范围与提示

样例1解释

对于第一条魔法地界：

生命值为$100$的盔甲收到$K_1$效果（$-100$）后的生命值为$0$，导致盔甲破碎。

生命值为$200$的盔甲每次收到效果后的生命值为：$100$,$1100$,$1660$。

生命值为$300$的盔甲每次收到效果后的生命值为：$200$,$1200$,$1760$​。

可见生命值为$200$的盔甲足以通过该段魔法地界，作为最优选择。

对于第二条魔法地界：

可证明不存在合适盔甲能够通过该段魔法地界。

对于第二条魔法地界：

可证明生命值为$200$的盔甲足以通过该段魔法地界，作为最优选择。

数据范围

对于$30$%的数据，$1 \leq N\leq 10^3$。

对于另外$20$%的数据，$0\leq K_{i,j}$。

对于$100$%的数据，$1 \leq N,T\leq 10^5，1 \leq \sum_{i=1}^{T}M_i\leq 10^6$，$0\leq H_i,\lvert K_{i,j} \rvert\leq10^9$。