冒险

【题目描述】

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

Introl 希望通过魔法地界后盔甲仍未破碎，并且他只会选择生命值最小且足够他通过该段魔法地界的盔甲。对于每段魔法地界，存在合法方案时输出选择的盔甲的生命值，不存在合法方案时输出 $-1$。

【输入格式】

第一行仅三个整数 $N$ 和 $T$。 第二行共 $N$ 个整数 $H_1, H_2 \dots H_N$。 第三行共 $T$ 个整数 $M_1, M_2 \dots M_T$。 接下来 $T$ 行，每行 $M_i$ 个整数 $K_{i,1}, K_{i,2} \dots K_{i,M_i}$。

【输出格式】

共 $T$ 行。存在合法方案时输出选择的盔甲的生命值，不存在合法方案时输出 $-1$。

【输入样例】

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

【输出样例】

200
-1
200

【样例解释】

对于第一条魔法地界，生命值为 100 的盔甲收到 $K_1$ 效果（$-100$）后生命值为 0，导致盔甲破碎；生命值为 200 的盔甲每次收到效果后的生命值为：100, 1100, 1660，可见生命值为 200 的盔甲足以通过该段魔法地界，作为最优选择。

对于第二条魔法地界，可证明不存在合适盔甲能够通过该段魔法地界。

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

【数据范围与提示】

• 对于 30% 的数据，$1 \le N \le 10^3$
• 对于另外 20% 的数据，$0 \le K_{i,j}$
• 对于 100% 的数据，$1 \le N, T \le 10^5$，$1 \le \sum_{i=1}^T M_i \le 10^6$，$0 \le H_i, |K_{i,j}| \le 10^9$

#include <cstdio>
#include ...

...

int main() {
  freopen("rush.in", "r", stdin);
  freopen("rush.out", "w", stdout);

  // 在这里开始编写你的代码

  return 0;
}