Hotel Reservation

Hongjun works at a travel agency. The agency must assign m men and f women to the given hotel rooms. Among these people, c male-female pairs are married couples. Each room has a maximum capacity and a rental cost.

The assignment must satisfy all of the following rules.

1. A man and a woman who are not married to each other cannot share a room.
2. If a married man and woman share a room, only those two people may stay in that room.
3. A married couple is not required to share a room.

Find the minimum total cost needed to assign rooms to everyone.

The first line contains four integers m (1 ≤ m ≤ 100), f (1 ≤ f ≤ 100), r (1 ≤ r ≤ 100), and c (0 ≤ c ≤ min(m, f)): the number of men, the number of women, the number of rooms, and the number of married couples.

Each of the next r lines contains two integers a and b, where 1 ≤ a ≤ 5 and 1 ≤ b ≤ 1000. Here, a is the maximum number of people who can stay in that room, and b is the cost of renting it.

If everyone can be assigned to rooms, print the minimum total rental cost. Otherwise, print Impossible.