It’s Halloween, and everyone in Halloween Town is excited! It’s so popular with the people there that the whole town is designed for Halloween. It has only one street (aptly named Trick-Or-Treat), with fifty thousand houses lined up all on the same side to make it convenient for trick-or-treating.
Bob lives in Halloween Town and he is getting prepared for tonight. He loves all kinds of candies except licorice flavoured candy. After a series of intensive calculation, he found out the (psycological) cost of carrying 1 gram of licorice candy in his trick-or-treating bag is exactly equal to the benefit of getting 1 gram of any other type of candy.
Of course trick-or-treating is no fun without friends. Bob has many friends that have chosen different trick-or-treating routes. Trick-or-treating routes all start at one house, end at another house down the street, and consist of all the houses in between (of course!). Clearly, Bob wants to have the most beneficial trick-or-treating night. He knows all the routes that his friends have chosen, and have a sheet of notes that tells him which house gives licorice candies, and how much candy each house gives away. (Yes, he took notes last year). Which friend should he go out trick-or-treating with tonight?
First there will be fifty thousand integers from -100 to 100, representing what kind and how much candy each house gives away. A negative number means licorice candies, while a positive number means any other kind of candy. The absolute value of the number represents the grams of candy given out. (Note: Halloween Town is a civilized town, and everyone counts from 0. i.e. the first number is for the 0th house, the last number for the 9999th house)
Then, there will be an integer n on the next line, representing the number of friends Bob have. Bob can have up to 50000 friends!
Finally, there will be n lines, each consisting of two numbers, representing the routes Bob’s friends are taking. (Again, the first pair is his 0th friend’s route). A pair of numbers a, b, means his friend will start at the ath house, and finish at the bth house, inclusive.
Output on the first line a number that represent the friend Bob should go out with.
Then, output on the second line a number equal to the net benefit of Bob, if he goes out with the friend above.
Sample data are available at http://www.ugrad.cs.ubc.ca/~cs490/questions/introQ1.in
2
25527
Sample data are available at http://www.ugrad.cs.ubc.ca/~cs490/questions/introQ1.test
36829
14481