SP13094 PCPC12H - Beggars

Begging nowadays is an organized profession and team work is extremely important. Beggars target special occasions to maximize revenue, such as Muslim Friday prayers. They wait outside the mosque until the prayer ends and ask people for money as people leave the mosque. In this problem you are to help two beggars to maximize their revenue on Friday after the Friday prayers. These beggars are experienced and know everything they need, specifically they know exactly when each mosque ends the prayer and how much money they will gain if at least one of them stands in front of that mosque when the prayer ends (there is no use if both of them stand at the same mosque). In their town there are n mosques on a straight line and you will be given the x coordinate for each mosque. The time needed for a beggar to travel from one mosque a to another mosque b is |xa-xb| units of time. As you know, these baggers are professionals and take no time to collect the money from a mosque if they happen to be there when the prayer ends, and can immediately start moving to another mosque. Of course the beggars can choose to initially start from any mosque. Your task here is to compute the maximum amount of money they can collect together. **Input Specification** Input contains multiple test cases. Each test case starts with number of mosques 1

N/A

N/A