题目描述
Introl有N件生命值分别为H1,H2......HN的盔甲。
他将通过T段长度分别为M1,M2.....MT的魔法地界中的某一条去异世界冒险,其经过Mi,j时盔甲会收到Ki,j的效果,当盔甲的生命值小于等于0时就会破碎。
Introl希望通过魔法地界后盔甲仍未破碎并且他只会选择生命值最小且足够他通过该段魔法地界的盔甲。
对于每段魔法地界,存在合法方案时输出选择的盔甲的生命值,不存在合法方案时输出−1。
输入格式
第一行仅三个整数N和T。
第二行共N个整数H1,H2......HN。
第三行共T个整数M1,M2......MT。
接下来T行,每行Mi个整数Ki,1,Ki,2......Ki,Mi
输出格式
共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的盔甲收到K1效果(−100)后的生命值为0,导致盔甲破碎。
生命值为200的盔甲每次收到效果后的生命值为:100,1100,1660。
生命值为300的盔甲每次收到效果后的生命值为:200,1200,1760。
可见生命值为200的盔甲足以通过该段魔法地界,作为最优选择。
对于第二条魔法地界:
可证明不存在合适盔甲能够通过该段魔法地界。
对于第二条魔法地界:
可证明生命值为200的盔甲足以通过该段魔法地界,作为最优选择。
数据范围
对于30%的数据,1≤N≤103。
对于另外20%的数据,0≤Ki,j。
对于100%的数据,1≤N,T≤105,1≤∑i=1TMi≤106,0≤Hi,∣Ki,j∣≤109。