B'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, ... , 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 '...