Explorer yy feels lucky that he has got N rather valuable chests by chance. But he had problem opening them. After doing some research for days, he has a clue. Let us number the chests from 1 to N, the chest with number i can be open in three ways:
1. Open it with the key with number Ai.
2. Open it with the crowbar with number Bi.
3. Just open it by force, doing that will decrease yy's HP by Di. yy will die if his HP is less or equal to zero.
Initially, yy has no keys and no crowbars, the tools are stored in a tower which is in the control of monsters. The tower has M floors, every floor can be considered as a 20x20 grids and contains at most two tools, and in case that it contains two tools, those two tools must be the same kind (i.e. both keys or crowbars). Each cell contains either a monster or a tool. If yy stands on a cell with tool, he can pick it up. But if the cell contains a monster, a fight will take place and cost his HP. After the battle this cell will turn into an empty one. On each floor there exist exactly one special "entry" cell, this cell is empty, when yy get to the floor, he will be teleported to that cell immediately. Note that yy can move upstairs or downstairs at any cell.
Once a tool get picked, it can be used arbitary times. It is guaranteed that every tool mentioned will appear at most once.
yy simply hates moving upstairs, as his friend, you're asked to calculate the minimum number of floors yy should go so that he can open all the N chests and still alive, and the minimum total HP cost in above case.