Quái vật và lọ thuốc

Có một dãy gồm $n$ ô được đánh số từ $1$ đến $n$ từ trái sang phải. Mỗi ô được mô tả bởi một số nguyên $a_j$:

• $a_j=0$: ô trống.
• $a_j<0$: ô chứa một quái vật có máu $-a_j$.
• $a_j>0$: ô chứa một lọ thuốc có giá trị $a_j$.

Trên dãy có $m$ anh hùng, anh hùng thứ $i$ đứng ở ô $s_i$ (ô này chắc chắn trống) và có $h_i$ máu. Các vị trí $s_i$ đôi một khác nhau.

Bạn cần chọn một ô tập kết (là một ô bất kỳ trong $n$ ô, có thể là ô trống, ô có quái vật hoặc ô có lọ thuốc), rồi lần lượt điều khiển từng anh hùng đi tới ô tập kết đó. Mỗi lần chỉ một anh hùng di chuyển; khi anh hùng đó đã tới ô tập kết mới điều khiển anh hùng tiếp theo.

Trong một lần di chuyển, anh hùng đi thẳng về phía ô tập kết theo từng ô một, không được đổi hướng hay đi lùi. Khi bước vào một ô:

• Ô trống: máu không đổi.
• Ô có quái vật máu $d$: nếu máu hiện tại của anh hùng $\ge d$ thì anh hùng thắng, máu bị trừ đi $d$ (anh hùng vẫn sống nếu máu về đúng $0$) và quái vật biến mất, ô trở thành trống. Nếu máu hiện tại $<d$ thì anh hùng thua và bạn thất bại.
• Ô có lọ thuốc giá trị $v$: máu anh hùng được cộng thêm $v$, lọ thuốc biến mất, ô trở thành trống.

Mọi thay đổi của dãy được giữ nguyên qua các lượt di chuyển kế tiếp: một quái vật đã bị tiêu diệt hay một lọ thuốc đã bị uống sẽ không còn nữa. Nhiều anh hùng có thể cùng đứng ở một ô.

Hãy chọn ô tập kết và thứ tự di chuyển sao cho mọi anh hùng đều tới được ô tập kết và còn sống, hoặc cho biết điều đó là không thể.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa $s_i$ và $h_i$.
• Dòng cuối chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Nếu không tồn tại cách chọn hợp lệ, in ra một số $-1$.

Ngược lại, in ra:

• Dòng đầu: chỉ số ô tập kết.
• Dòng thứ hai: $m$ số nguyên là thứ tự di chuyển của các anh hùng (đánh số từ $1$ đến $m$ theo thứ tự trong dữ liệu vào).

Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Ràng buộc

• $1\le n\le 100$; $1\le m\le n$.
• $1\le s_i\le n$, các $s_i$ đôi một khác nhau, mỗi ô $s_i$ là ô trống.
• $1\le h_i\le {10}^6$.
• $-{10}^6\le a_j\le {10}^6$.

Ví dụ