{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePolycarp 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 \u003cspan class\u003d\"tex-font-style-it\"\u003eblank\u003c/span\u003e cell (it contains neither a monster nor a potion).\u003c/p\u003e\u003cp\u003ePolycarp has $$$m$$$ tokens representing heroes fighting monsters, which are initially located in the blank cells $$$s_1, s_2, \\dots, s_m$$$. Polycarp\u0027s 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.\u003c/p\u003e\u003cp\u003eAfter 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.\u003c/p\u003e\u003cp\u003eInitially 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.\u003c/p\u003e\u003cp\u003eIf a hero steps into a cell which is blank (i.e. doesn\u0027t contain a monster/potion), hero\u0027s HP does not change.\u003c/p\u003e\u003cp\u003eIf a hero steps into a cell containing a monster, then the hero and the monster fight. If monster\u0027s HP is strictly higher than hero\u0027s HP, then the monster wins and Polycarp loses the whole game. If hero\u0027s HP is greater or equal to monster\u0027s HP, then the hero wins and monster\u0027s HP is subtracted from hero\u0027s 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.\u003c/p\u003e\u003cp\u003eIf a hero steps into a cell containing a potion, then the hero drinks the potion immediately. As a result, potion\u0027s HP is added to hero\u0027s HP, the potion disappears, and the cell becomes blank.\u003c/p\u003e\u003cp\u003eObviously, 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.\u003c/p\u003e\u003cp\u003eHelp Polycarp write a program to choose a rally point and the order in which heroes move.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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.\u003c/p\u003e\u003cp\u003eThe 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. \u003c/p\u003e\u003cp\u003eThe 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:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$a_j\u003d0$$$ means that the $$$i$$$-th cell is blank, \u003c/li\u003e\u003cli\u003e $$$a_j\u0026lt;0$$$ means that the $$$i$$$-th cell contains monster with positive HP of $$$-a_j$$$, \u003c/li\u003e\u003cli\u003e $$$a_j\u0026gt;0$$$ means that the $$$i$$$-th cell contains potion with $$$a_j$$$ HP. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOn the first line of the output print the index of the rally point cell.\u003c/p\u003e\u003cp\u003eOn 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.\u003c/p\u003e\u003cp\u003eIf there are multiple solutions, print any of them.\u003c/p\u003e\u003cp\u003eIf it is impossible to find a rally point which can be reached by all heroes, print a single integer \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e in the output.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e8 3\n8 2\n1 3\n4 9\n0 3 -5 0 -5 -4 -1 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n3 1 2 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 1\n1 1\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2\n1 1\n3 1\n0 -5000 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e8 3\n1 15\n5 10\n8 1\n0 -5 -5 -5 0 -5 -5 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\n2 1 3 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe picture illustrates the first example:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/4a8998611ad7f88adcca499a0330bdcb?v\u003d1715616468\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e"}}]}