It is said that there are many spirits in Lotus Land like to hang out in winter. Now the winter is revealing, and many spirits are playing tricks in Lotus Land. Reimu, who should have to deal with
It is said that there are many spirits in Lotus Land like to hang out in winter. Now the winter is revealing, and many spirits are playing tricks in Lotus Land. Reimu, who should have to deal with it, is lying at home, entrusting this matter to Marisa. Unfortunately, Marisa is suddenly ill, so she entrusts this matter to Alice. Since it's Marisa’s invitation, Alice will certainly not refuse. Therefore, she is considering how to get rid of these spirits. Alice has many puppet soldiers. She divides them into m armies based on their weapons. Each army has the same kind of weapon. There are three kinds of weapons: sword, shield and bow (respectively represented by S, D and B). Each army has two attribute values, which respectively represents the power and durability of the army. After investigation, Alice found that there are n spirits in total,each of which had its own power and weapon. The three kinds of weapons restrict each other (Sword restricts shield, shield restricts bow and bow restricts sword). When a weapon is restricted, the power of this party will be reduced by fifty percent during the battle. For convenience, Alice wants to defeat them one by one, that is, if she wants to attack the kth sprite, he must defeat the (k-1)th sprite (k>1). If the power of Alice 's army is ai and the sprite’s power is bi, Alice 's army can win the battle only when ai ≥ bi. Each battle will consume one durability of the army. When the durability drops to 0 or Alice fails a battle, she must return to rectify and remake those soldiers (See the example below). Assume that Alice can only lead exactly one army to fight at a time and after each battle, Alice will repair her puppet soldiers immediately. The problem is, how many times does Alice have to return at least?