Ninja

PROBLEM STATEMENT

Hollywood portrays an interesting version of reality.  For example, all phone
numbers start with the local code 555, and if you jump in the air next to an
explosion, you will be fine.

You are proposing a theory to the Academy of Hollywood Physics.  You have
noticed in all the movies you have watched that when Hollywood "Ninjas" go to
battle in large groups, they invariably just get thrown around and beaten by
the hero.  However, a single "Ninja" can destroy armies of entire countries.
You believe from the empirical evidence that the power of Hollywood "Ninjas"
actually varies inversely with the number of Ninjas in the group.  You propose
the Inverse Ninja Rule: an equation exists such that some integer constant c
(between 1 and 1,000,000,000, inclusive), divided by the number of Ninjas
raised to the power of some other integer constant p (between 1 and 4,
inclusive) will (after rounding the result down to the nearest integer) predict
the number of enemies the "Ninjas" will kill in all movies from the same
director:

	(c / ((ninjas)^p)) = kills

Create a class Ninja containing a method inverse that takes a list of strings
containing statistics from previous movies from the same director and an
integer telling you how many "Ninjas" will be in the group in the director's
next movie.  These statistics will be strings in the form of "<N> <K>" (quotes
and angle braces are included for clarity only), where N is the number of
Ninjas in that group (between 1 and 100, inclusive), and K is the number of
people they killed (between 0 and 10,000, inclusive).  Use your Inverse Ninja
equation to predict how many people will be killed by the group of "Ninjas"
this time, or return -1 if this can not be determined by the Inverse Ninja Rule.


DEFINITION
Class: Ninja
Method: inverse
Parameters: String[], int
Returns: int
Method signature (be sure your method is public):  int inverse(String[]
statistics, int ninjas);


HELPFUL MATH HINT
Keep in mind that integer division is not one-to-one.  That is, many different
numbers divided by a single number may result in the same result.  For example,
both 4/3 and 5/3 result in 1 with integer division.  For a given denominator D
(the number you are dividing by), you can compute the range of possible
numerators N (the number you are dividing into) that will net a result of R as
being from (and including) N=R*D to (and NOT including) N=(R+1)*D.  For example
with a denominator of 4 (D=4), and a target result of 3 (R=3), the range of
possible numerators is from (and including) 12 (R*D = 3*4) to (and NOT
including) 16 ((R+1)*D) = (3+1)*4 = 4*4).  In other words, 12, 13, 14 or 15
would all net 3 if integer divided by 4.

NOTES
- Due to rounding, if some statistics have different numbers of "Ninjas"
killing the same number of people, the Inverse Ninja Rule may still apply.
However, if some statistics have different groups of the same number of
"Ninjas" killing different numbers of people, it must not apply - and your
method should return -1.
- Values for constants c and p that are out of the above-given bounds are not
valid solutions - even if they do work numerically.
- Note that it is possible for the return value to be larger than 10,000, but
it can not be larger than 1,000,000,000.  You do not need to check for this
specifically, the numbers will just work out this way.
- If there is not enough information given in statistics to accurately
calculate this value, you should return the special value -1 (See Example #2
and Example #3).
- If the statistics alone prove that the Inverse Ninja Rule does not apply,
return the special value -1 (See Example #4).

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:
- There will be between 1 and 50 entries in statistics - though they are in no
particular order and values may be repeated.
- Each string in statistics will be in the form of "<N> <K>" (quotes and angle
braces are included for clarity only), where N is the number of Ninjas in that
group (between 1 and 100, inclusive), and K is the number of people they killed
(between 0 and 10,000, inclusive).  Each number may have leading zeros.
- ninjas will simply be an integer from 1 to 100 (inclusive) containing the
number of "Ninjas" that will be in the next group.


EXAMPLES

In each of these examples, quotes ('"') and parenthesis ('(' and ')') are
included for clarity only.  They are never part of the input or output.

Example #1)
statistics = {"100 1", "10 10", "1 100"}
ninjas = 3
return 33
You can determine that c is 100 (since, by the last statistic, one Ninja kills
100, no matter what p is c must be 100) and p is 1 (since, with c=100, no other
value for p will work with the first or second statistic).  Since 100/3^1 =
33.3333, you know the answer is 33.

Example #2)
statistics = {"1 1000"}
ninjas = 3
return -1
You can determine that c is 1000, but p can be 1, 2, 3 or 4.  Since 1000/3^1 =
333.3333 and 1000/3^4 = 12.3456, (i.e.: 333, and 12), you can see that you can
not determine the correct result.

Example #3)
statistics = {"8 100", "16 50"}
ninjas = 4
return -1
You can determine that p is 1 and c is between 800 and 807 (inclusive).  Since,
for 4 Ninjas, some of these values will result in an answer of 200, and others
in 201, you can't predict the outcome exactly.

Example #4)
statistics = {"10 20", "10 30"}
ninjas = 20
return -1
The first statistic contradicts the second.  Apparently this director does not
live by the Inverse Ninja Rule.

Example #5)
statistics = {"1 0"}
ninjas = 1
return -1
This would work (and return 0) if c is 0 and p is anything, but according to
the Inverse Ninja Rule, c must be at least 1, so it does not apply.

Example #6)
statistics = {"4 200", "8 100"}
ninjas = 16
return 50

Example #7)
statistics = {"10 100", "100 1"}
ninjas = 15
return 44