CF1070G.Monsters and Potions

Polycarp is an introvert person. In fact he is so much of an introvert that he plays "Monsters and Potions" board game alone. The board of the game is a row of $n$ cells. The cells are numbered from $1$ to $n$ from left to right. There are three types of cells: a cell containing a single monster, a cell containing a single potion or a blank cell (it contains neither a monster nor a potion).

Polycarp has $m$ tokens representing heroes fighting monsters, which are initially located in the blank cells $s_1, s_2, \dots, s_m$. Polycarp's task is to choose a single cell (rally point) and one by one move all the heroes into this cell. A rally point can be a cell of any of three types.

After Policarp selects a rally point, he picks a hero and orders him to move directly to the point. Once that hero reaches the point, Polycarp picks another hero and orders him also to go to the point. And so forth, until all the heroes reach the rally point cell. While going to the point, a hero can not deviate from the direct route or take a step back. A hero just moves cell by cell in the direction of the point until he reaches it. It is possible that multiple heroes are simultaneously in the same cell.

Initially the $i$-th hero has $h_i$ hit points (HP). Monsters also have HP, different monsters might have different HP. And potions also have HP, different potions might have different HP.

If a hero steps into a cell which is blank (i.e. doesn't contain a monster/potion), hero's HP does not change.

If a hero steps into a cell containing a monster, then the hero and the monster fight. If monster's HP is strictly higher than hero's HP, then the monster wins and Polycarp loses the whole game. If hero's HP is greater or equal to monster's HP, then the hero wins and monster's HP is subtracted from hero's HP. I.e. the hero survives if his HP drops to zero, but dies (and Polycarp looses) if his HP becomes negative due to a fight. If a hero wins a fight with a monster, then the monster disappears, and the cell becomes blank.

If a hero steps into a cell containing a potion, then the hero drinks the potion immediately. As a result, potion's HP is added to hero's HP, the potion disappears, and the cell becomes blank.

Obviously, Polycarp wants to win the game. It means that he must choose such rally point and the order in which heroes move, that every hero reaches the rally point and survives. I.e. Polycarp loses if a hero reaches rally point but is killed by a monster at the same time. Polycarp can use any of $n$ cells as a rally point — initially it can contain a monster, a potion, or be a blank cell with or without a hero in it.

Help Polycarp write a program to choose a rally point and the order in which heroes move.

波利卡普是一个性格内向的人。事实上，他内向到甚至独自一人玩桌游《怪物与药水》。游戏棋盘是一行 $n$ 个格子，从左至右依次编号为 $1$ 到 $n$。格子共有三种类型：含有一只怪物的格子、含有一瓶药水的格子，以及空格子（既不含怪物也不含药水）。

波利卡普拥有 $m$ 个代表英雄的棋子，初始时位于若干空格子 $s_1, s_2, \dots, s_m$ 上。波利卡普的任务是选定一个格子（集结点），并逐一将所有英雄移动至该格子。集结点可以是任意一种类型的格子（怪物格、药水格或空格）。

波利卡普选定集结点后，先挑选一名英雄，命令其直接前往该点；待该英雄抵达后，再挑选另一名英雄，同样命令其前往该点；依此类推，直至所有英雄均抵达集结点。英雄在前往集结点途中不得偏离直线路径，也不得后退——他们只能沿朝向集结点的方向逐格移动，直至到达。多个英雄可同时处于同一格子中。

初始时，第 $i$ 位英雄具有 $h_i$ 点生命值（HP）。怪物也具有 HP，不同怪物的 HP 可能不同；药水同样具有 HP，不同药水的 HP 也可能不同。

• 若英雄踏入一个空格子（即不含怪物/药水），其 HP 不发生变化；
• 若英雄踏入一个含怪物的格子，则英雄与怪物发生战斗：
  • 若怪物 HP 严格大于 英雄 HP，则怪物获胜，波利卡普立即输掉整局游戏；
  • 若英雄 HP 大于等于 怪物 HP，则英雄获胜，怪物 HP 从英雄 HP 中扣除。换言之，若英雄 HP 降至 0，其仍存活；但若因战斗导致 HP 变为负数，则英雄死亡（波利卡普输掉游戏）。英雄战胜怪物后，该怪物消失，对应格子变为空格；
• 若英雄踏入一个含药水的格子，则英雄立即饮下该药水，药水 HP 加入英雄 HP，药水消失，对应格子变为空格。

显然，波利卡普希望赢得游戏。这意味着他必须选择一个集结点，并确定英雄移动的顺序，使得每位英雄均能成功抵达集结点且全程存活。特别地，若某位英雄抵达集结点的同时被该格子中的怪物击杀，则波利卡普判负。波利卡普可任选 $n$ 个格子之一作为集结点——该格子初始时可以是怪物格、药水格，或空格（无论其上是否已有英雄）。

请帮助波利卡普编写一个程序，为其选出合适的集结点及英雄移动顺序。

The first line of the input contains two integers $n$ and $m$ ($1 \le n \le 100$; $1 \le m \le n$) — length of the game board and the number of heroes on it.

The following $m$ lines describe heroes. Each line contains two integers $s_i$ and $h_i$ ($1 \le s_i \le n$; $1 \le h_i \le 10^6$), where $s_i$ is the initial position and $h_i$ is the initial HP of the $i$-th hero. It is guaranteed that each cell $s_i$ is blank. It is also guaranteed that all $s_i$ are different.

The following line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^6 \le a_j \le 10^6$), where $a_j$ describes the $i$-th cell of the game board:

• $a_j=0$ means that the $i$-th cell is blank,
• $a_j \lt 0$ means that the $i$-th cell contains monster with positive HP of $-a_j$,
• $a_j \gt 0$ means that the $i$-th cell contains potion with $a_j$ HP.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 100$；$1 \le m \le n$），分别表示游戏棋盘的长度以及其上的英雄数量。

接下来的 $m$ 行描述各个英雄。每行包含两个整数 $s_i$ 和 $h_i$（$1 \le s_i \le n$；$1 \le h_i \le 10^6$），其中 $s_i$ 表示第 $i$ 个英雄的初始位置，$h_i$ 表示其初始生命值（HP）。保证每个位置 $s_i$ 均为空格（即无其他实体）。同时保证所有 $s_i$ 互不相同。

随后的一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^6 \le a_j \le 10^6$），其中 $a_j$ 描述棋盘上第 $j$ 个格子的状态：

• $a_j = 0$ 表示第 $j$ 个格子为空；
• $a_j < 0$ 表示第 $j$ 个格子中有一只怪物，其生命值为 $-a_j$（正值）；
• $a_j > 0$ 表示第 $j$ 个格子中有一瓶药水，可恢复 $a_j$ 点生命值。

On the first line of the output print the index of the rally point cell.

On the second line print $m$ integers — the order in which heroes should move to the rally point. Heroes are numbered from $1$ to $m$ in the order they are given in the input.

If there are multiple solutions, print any of them.

If it is impossible to find a rally point which can be reached by all heroes, print a single integer -1 in the output.

在输出的第一行打印集合点格子的索引。

在第二行打印 $m$ 个整数——英雄们前往集合点的顺序。英雄按输入中给出的顺序编号为 $1$ 至 $m$。

若存在多个解，输出任意一个即可。

若无法找到一个所有英雄均能到达的集合点，则在输出中单独打印整数 $-1$。

The picture illustrates the first example:

该图展示了第一个示例：