**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Three problems numbered 6 through 8
**********************************************************************

Problem 6: Protecting the Flowers [Christos Tzamos, 2007]

Farmer John went to cut some wood and left N (2 <= N <= 100,000)
cows eating the grass, as usual. When he returned, he found to his
horror that the cluster of cows was in his garden eating his beautiful
flowers. Wanting to minimize the subsequent damage, FJ decided to take
immediate action and transport each cow back to its own barn.

Each cow i is at a location that is Ti minutes (1 <= Ti <= 2,000,000)
away from its own barn. Furthermore, while waiting for transport, she
destroys Di (1 <= Di <= 100) flowers per minute. No matter how hard
he tries, FJ can only transport one cow at a time back to her barn.
Moving cow i to its barn requires 2*Ti minutes (Ti to get there and
Ti to return). FJ starts at the flower patch, transports the cow to its
barn, and then walks back to the flowers, taking no extra time to get to
the next cow that needs transport.

Write a program to determine the order in which FJ should pick up
the cows so that the total number of flowers destroyed is minimized.

PROBLEM NAME: flowers

INPUT FORMAT:

* Line 1: A single integer N

* Lines 2..N+1: Each line contains two space-separated integers, Ti
        and Di, that describe a single cow's characteristics

SAMPLE INPUT (file flowers.in):

6
3 1
2 5
2 3
3 2
4 1
1 6


OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of destroyed
        flowers

SAMPLE OUTPUT (file flowers.out):

86

OUTPUT DETAILS:

FJ returns the cows in the following order: 6, 2, 3, 4, 1, 5. While
he is transporting cow 6 to the barn, the others destroy 24 flowers;
next he will take cow 2, losing 28 more of his beautiful flora. For
the cows 3, 4, 1 he loses 16, 12, and 6 flowers respectively. When
he picks cow 5 there are no more cows damaging the flowers, so the
loss for that cow is zero. The total flowers lost this way is 24 +
28 + 16 + 12 + 6 = 86.

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

Problem 7: Tallest Cow [Brian Dean, 2006]

FJ's N (1 <= N <= 10,000) cows conveniently indexed 1..N are standing
in a line.  Each cow has a positive integer height (which is a bit
of secret). You are told only the height H (1 <= H <= 1,000,000)
of the tallest cow along with the index I of that cow.

FJ has made  a list of R (0 <= R <= 10,000) lines of the form "cow
17 sees cow 34". This means that cow 34 is at least as tall as cow
17, and that every cow between 17 and 34 has a height that is
strictly smaller than that of cow 17.

For each cow from 1..N, determine its maximum possible height, such
that all of the information given is still correct. It is guaranteed
that it is possible to satisfy all the constraints.

PROBLEM NAME: tallest

INPUT FORMAT:

* Line 1: Four space-separated integers: N, I, H and R

* Lines 2..R+1: Two distinct space-separated integers A and B (1 <= A,
        B <= N), indicating that cow A can see cow B.

SAMPLE INPUT (file tallest.in):

9 3 5 5
1 3
5 3
4 3
3 7
9 8


INPUT DETAILS:

There are 9 cows, and the 3rd is the tallest with height 5.

OUTPUT FORMAT:

* Lines 1..N: Line i contains the maximum possible height of cow i.

SAMPLE OUTPUT (file tallest.out):

5
4
5
3
4
4
5
5
5

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

Problem 8: Balanced Lineup [Coaches, 2004]

For the daily milking, Farmer John's N cows (1 <= N <= 50,000)
always line up in the same order. One day Farmer John decides to
organize a game of Ultimate Frisbee with some of the cows. To keep
things simple, he will take a contiguous range of cows from the
milking lineup to play the game. However, for all the cows to have
fun they should not differ too much in height.

Farmer John has made a list of Q (1 <= Q <= 200,000) potential
groups of cows and their heights (1 <= height <= 1,000,000). For
each group, he wants your help to determine the difference in height
between the shortest and the tallest cow in the group.

PROBLEM NAME: lineup

INPUT FORMAT:

* Line 1: Two space-separated integers, N and Q.

* Lines 2..N+1: Line i+1 contains a single integer that is the height
        of cow i

* Lines N+2..N+Q+1: Two integers A and B (1 <= A <= B <= N),
        representing the range of cows from A to B inclusive.

SAMPLE INPUT (file lineup.in):

6 3
1
7
3
4
2
5
1 5
4 6
2 2


OUTPUT FORMAT:

* Lines 1..Q: Each line contains a single integer that is a response
        to a reply and indicates the difference in height between the
        tallest and shortest cow in the range.

SAMPLE OUTPUT (file lineup.out):

6
3
0

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