CF1070G Monsters and Potions
题目描述
有 $n$ 个位置排成一排，每个位置上有一个数 $a_i$。有 $m$ 个英雄，分布在所有数为 $0$ 的位置上，每个英雄有一个生命值。每个位置至多有一个英雄，但有可能没有英雄。
你需要选定一个位置作为集合点。并依次指定每个英雄（自己决定顺序）直接走到集合点。当一个英雄走入一个位置 $i$ 时，他的生命值会加上 $a_i$，并把这个位置上的数变为 $0$。特别的，生命值不能为负数（可以为 $0$）。
你需要找到一种方法，使得所有英雄都能够到达集合点。
输入格式
第一行两个数 $n$ 和 $m$。$(1\leq m\leq n\leq 100)$
接下来 $m$ 行，每行两个数 $s_i$ 和 $h_i$，表示一个英雄的位置和生命值。 $(1\leq s_i\leq n,1\leq h_i\leq 10^6)$
接下来一行 $n$ 个数，表示 $a_i$。
输出格式
如果有解，第一行一个数，表示集合点的位置。
接下来一行 $m$ 个数，表示依次选取英雄的顺序。（输出编号）
如果无解，输出 `-1`。
说明/提示
The picture illustrates the first example:
