Galley Pigs P13333


Statement
 

pdf   zip

Contact with the Americas revolutionized many aspects of life in Europe. Time-honoured traditions and practices that had held for centuries were dramatically changed as new materials, skills, and even vegetables and animals were sailed across the ocean and introduced into societies that had never seen change of that magnitude until then.

0.78

And the art of sailing was one which experienced such an unprecedented revolution after guinea pigs were first encountered by Europeans exploring the Andean region. On their trip back, captains realized that with an ingenious assembly of wheels, axles, and belts, they could propel their galleys in a much more efficient way than with human rowers. Guinea pigs ate in smaller quantities, grain for feeding them was easier to transport, and they were much less likely to organize mutinies that would end with the captain’s head at the end of an oar…

0.22

0.6

The system consisted of a propeller wheel, which moved the ship, together with a series of auxiliary wheels, on which guinea pigs ran to provide the propulsion force. Each wheel had an axle, where one or more transmission belts connected it to other wheels.

0.4

In their race for sailing advantage, seafarers quickly learned to identify the sturdiest and fastest of the rodents, fighting for them in auctions or even resorting to burglary in order to steal them from vessels moored at neighbouring piers. However, greed for speed remained as dangerous as it was with human propulsion: if at any point one of the pigs was pushed to run beyond their maximum natural speed, the poor animal would perish in an ear-piercing squeak of death.

Can you help these optimizing navigators determine if their furry crew will be able to propel their boat without any casualties?

Input

Input consists of several cases. Each case starts with the number of wheels 2≤W≤1042 \le W \le 10^4 and the number of belts 1≤B≤2⋅1041 \le B \le 2 \cdot 10^4.

0.45 After that come WW lines, one for each wheel. The line for a wheel 0≤w<W0 \le w < W contains the name of the guinea pig that will be on it, the axle and rim radii, both between 1 and 1000, and the maximum speed, between 1 and 10410^4, that the animal can run at.

0.55