**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Two problems numbered 6 through 7
**********************************************************************

Problem 6: Close Encounter [Hal Burch, 2005]

Lacking even a fifth grade education, the cows are having trouble
with a fraction problem from their textbook. Please help them.  The
problem is simple:

    Given a properly reduced fraction (i.e., the greatest common divisor of 
    the numerator and denominator is 1, so the fraction cannot be further 
    reduced) find the smallest properly reduced fraction with numerator and
    denominator in the range 1..32,767 that is closest (but not equal)
    to the given fraction.

PROBLEM NAME: nearfr

INPUT FORMAT:

* Line 1: Two positive space-separated integers N and D (1 <= N < D <=
        32,767), respectively the numerator and denominator of the
        given fraction

SAMPLE INPUT (file nearfr.in):

2 3

INPUT DETAILS:

2/3

OUTPUT FORMAT:

* Line 1: Two space-separated integers, respectively the numerator and
        denominator of the smallest, closest fraction different from
        the input fraction.

SAMPLE OUTPUT (file nearfr.out):

21845 32767

OUTPUT DETAILS:

21845/32767 = .666676839503.... ~ 0.666666.... = 2/3.

**********************************************************************

Problem 7: Allowance [Brian Dean, 2004]

As a reward for record milk production, Farmer John has decided to
start paying Bessie the cow a small weekly allowance. FJ has a set
of coins in N (1 <= N <= 20) different denominations, where each
denomination of coin evenly divides the next-larger denomination
(e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins).
Using the given set of coins, he would like to pay Bessie at least
some given amount of money C (1 <= C <= 100,000,000) every week.
Please help him compute the maximum number of weeks he can pay
Bessie.

PROBLEM NAME: allow

INPUT FORMAT:

* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Each line corresponds to a denomination of coin and
        contains two integers: the value V (1 <= V <= 100,000,000) of
        the denomination, and the number of coins B (1 <= B <=
        1,000,000) of this denomation in Farmer John's possession.

SAMPLE INPUT (file allow.in):

3 6
10 1
1 100
5 120

INPUT DETAILS:

FJ would like to pay Bessie 6 cents per week.  He has 100 1-cent coins,
120 5-cent coins, and 1 10-cent coin.

OUTPUT FORMAT:

* Line 1: A single integer that is the number of weeks Farmer John can
        pay Bessie at least C allowance

SAMPLE OUTPUT (file allow.out):

111

OUTPUT DETAILS:

FJ can overpay Bessie with the one 10-cent coin for 1 week, then pay Bessie
two 5-cent coins for 10 weeks and then pay Bessie one 1-cent coin and one
5-cent coin for 100 weeks.

**********************************************************************