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, $c$ and $C$, respectively. At least $c$ people are required to live on a floor to ensure that the floor is utilized to its full potential. At most $C$ 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.

Input Specification

The first line contains four integers, $M$ $(1\le M\le 100000)$, $N$ $(1\le N\le 100000)$, $c$ $(0\le c\le 500)$, and $C$ $(c\le C\le 500)$, where $M$ is the dimension of the grid in the north-south direction, $N$ is the dimension of the grid in the east-west direction, $c$ and $C$ are the minimum and maximum number of people allowed per floor.

Each of the next $M$ lines contains exactly one integer in $[0,20000]$. Together, they specify the western skyline. After this, the next $N$ lines specify the southern skyline in the same way.

Output Specification

The output contains the minimum and maximum number of people that could be living in Skytown. Both numbers are guaranteed to fit in a $32$-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.

Sample Input

5 10 10 20
2
4
6
8
10
1
2
3
4
5
6
7
8
9
10

Sample Output

Minimum: 550, maximum: 4100