MIT ACM Practice Contest: Feb 26, 2005
Modern cities often contain densely packed skyscrapers arranged neatly on a rectangular grid of streets and avenues. Skytown is no exception. The city has grown tremendously in the past few years. New skyscrapers, ever taller than previous skyscrapers, are constantly being erected with great haste. The skyscrapers have all been constructed identically, of course with the exception that some skyscrapers are taller than others. According to city regulations, each floor of a skyscraper has some minimum and maximum capacity, and , respectively. At least people are required to live on a floor to ensure that the floor is utilized to its full potential. At most people are permitted to live on a floor to prevent overcrowding.
Because Skytown has grown so fast, the mayor wanted to boast about the city's soaring population. The only problem is that he hasn't the faintest clue how many people live in Skytown. He has put you in charge of estimating the city's population. Of course, being a programmer, you seek a programming solution and do not want to go around the entire city asking how many people live on each floor. You come up with the following simple strategy: you will record the skyline as viewed from both the south and the west. The skyline from the south is computed as follows: for each line of skyscrapers running north-south, the highest one in that line is recorded.
Given this data, compute the minimum and maximum number of people that could be living Skytown.
The first line contains four integers, , , , and , where is the dimension of the grid in the north-south direction, is the dimension of the grid in the east-west direction, and are the minimum and maximum number of people allowed per floor.
Each of the next lines contains exactly one integer in . Together, they specify the western skyline. After this, the next lines specify the southern skyline in the same way.
The output contains the minimum and maximum number of people that could
be living in Skytown. Both numbers are guaranteed to fit in a -bit
signed integer. If the two skylines specified in the input are
consistent, that is, cannot possibly describe a possible configuration
of skyscrapers, print
Impossible on a single line.
5 10 10 20 2 4 6 8 10 1 2 3 4 5 6 7 8 9 10
Minimum: 550, maximum: 4100