Statement

Bug colonies have been the center of attention of scientists for a long time. Through some technological advancements, we are now able to describe a bug colony using a number known as the degree of the colony. A colony of degree 0 or 1 represents a colony with one bug. A colony of degree i > 1 is obtained by merging a colony of degree i - 1 together with a colony of degree i - 2. As such, a colony of degree 2 has two bugs, a colony of degree 3 has three bugs, a colony of degree 4 has five bugs and so on. Marco owns the biggest bug farm in the world, having at his disposal a virtually infinite amount of colonies of any degree. Every day he receives N offers, each described by two numbers A_i and B_i, meaning that he can sell as many colonies of degree A_i as he wants and get B_i money for each colony of that degree...