CF521D Shop

Vasya plays one very well-known and extremely popular MMORPG game. His game character has $ k $ skill; currently the $ i $ -th of them equals to $ a_{i} $ . Also this game has a common rating table in which the participants are ranked according to the product of all the skills of a hero in the descending order. Vasya decided to 'upgrade' his character via the game store. This store offers $ n $ possible ways to improve the hero's skills; Each of these ways belongs to one of three types: 1. assign the $ i $ -th skill to $ b $ ; 2. add $ b $ to the $ i $ -th skill; 3. multiply the $ i $ -th skill by $ b $ . Unfortunately, a) every improvement can only be used once; b) the money on Vasya's card is enough only to purchase not more than $ m $ of the $ n $ improvements. Help Vasya to reach the highest ranking in the game. To do this tell Vasya which of improvements he has to purchase and in what order he should use them to make his rating become as high as possible. If there are several ways to achieve it, print any of them.

N/A

N/A